제출 #1295114

#제출 시각아이디문제언어결과실행 시간메모리
1295114k12_khoi별들과 삼각형 (IZhO11_triangle)C++17
100 / 100
197 ms28924 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define X first #define Y second const int N=3e5+5; int n,x,y; ll res; int cnt[N],dem[N]; vector <int> ve,comp,temp; vector <pii> a; vector <pii> query_x[N],queryY[N]; int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); ve.clear(); comp.clear(); a.clear(); cin >> n; for (int i=0;i<n;i++) { cin >> x >> y; ve.push_back(x); comp.push_back(y); a.push_back(make_pair(x,y)); } sort(ve.begin(),ve.end()); ve.resize(unique(ve.begin(),ve.end())-ve.begin()); sort(comp.begin(),comp.end()); comp.resize(unique(comp.begin(),comp.end())-comp.begin()); for (int i=0;i<n;i++) { a[i].X=lower_bound(ve.begin(),ve.end(),a[i].X)-ve.begin(); a[i].Y=lower_bound(comp.begin(),comp.end(),a[i].Y)-comp.begin(); query_x[a[i].X].push_back(make_pair(a[i].Y,i)); queryY[a[i].Y].push_back(make_pair(a[i].X,i)); } for (int i=0;i<ve.size();i++) { temp.clear(); for (pii j:query_x[i]) temp.push_back(j.X); sort(temp.begin(),temp.end()); temp.resize(unique(temp.begin(),temp.end())-temp.begin()); for (int i=0;i<=temp.size();i++) cnt[i]=0; for (int j=0;j<query_x[i].size();j++) { query_x[i][j].X=lower_bound(temp.begin(),temp.end(),query_x[i][j].X)-temp.begin(); cnt[query_x[i][j].X]++; } for (int i=temp.size()-1;i>=0;i--) cnt[i]+=cnt[i+1]; for (pii j:query_x[i]) dem[j.Y]=cnt[0]-cnt[j.X]+cnt[j.X+1]; } for (int i=0;i<comp.size();i++) { temp.clear(); for (pii j:queryY[i]) temp.push_back(j.X); sort(temp.begin(),temp.end()); temp.resize(unique(temp.begin(),temp.end())-temp.begin()); for (int i=0;i<=temp.size();i++) cnt[i]=0; for (int j=0;j<queryY[i].size();j++) { queryY[i][j].X=lower_bound(temp.begin(),temp.end(),queryY[i][j].X)-temp.begin(); cnt[queryY[i][j].X]++; } for (int i=temp.size()-1;i>=0;i--) cnt[i]+=cnt[i+1]; for (pii j:queryY[i]) res+=1LL*(cnt[0]-cnt[j.X]+cnt[j.X+1])*dem[j.Y]; } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...