Submission #218250

#TimeUsernameProblemLanguageResultExecution timeMemory
218250algorithm16Plahte (COCI17_plahte)C++14
0 / 160
707 ms524292 KiB
#include<iostream> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; vector <pair<pair<int,int>,pair<int,int> > > v,v4; vector <int> v2,t[500005],p[500005],v3[80005]; vector <pair<int,int> > v1[160005]; int off=1,parent[160005],cnt1[80005]; map <pair<int,int>,int> m1; set <int> dfs(int x) { //cout << x << "\n"; set <int> ret,s; if(v[x].second.first==-1) { ret.insert(m1[v[x].first]); return ret; } for(int i=0;i<v3[x].size();i++) { s=dfs(v3[x][i]); if(ret.size()<s.size()) swap(ret,s); for(set <int>::iterator it=s.begin();it!=s.end();it++) { ret.insert(*it); } } cnt1[x]=ret.size(); return ret; } void send(int x) { if(p[x].size()==0) return; for(int i=0;i<p[x].size();i++) { if(p[x][i]>0) t[x].push_back(p[x][i]); else t[x].pop_back(); } if(x<off) { for(int i=0;i<p[x].size();i++) { p[x*2].push_back(p[x][i]); p[x*2+1].push_back(p[x][i]); } } p[x].clear(); } void update(int x,int lo,int hi,int l,int r,int v) { if(lo>r or hi<l) return; if(lo>=l && hi<=r) { p[x].push_back(v); send(x); return; } update(x*2,lo,(lo+hi)/2,l,r,v); update(x*2+1,(lo+hi)/2+1,hi,l,r,v); } int query(int x,int lo,int hi,int l,int r) { send(x); if(lo>r or hi<l) return -1; if(lo>=l && hi<=r) { if(!t[x].empty()) return t[x].back(); return -1; } return max(query(x*2,lo,(lo+hi)/2,l,r),query(x*2+1,(lo+hi)/2+1,hi,l,r)); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m,ind=0,cnt=0; cin >> n >> m; for(int i=0;i<n;i++) { int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; v2.push_back(x1); v2.push_back(x2); v2.push_back(y1); v2.push_back(y2); v.push_back(make_pair(make_pair(x1,y1),make_pair(x2,y2))); } for(int i=0;i<m;i++) { int x,y,c; cin >> x >> y >> c; m1[make_pair(x,y)]=c; v2.push_back(x); v2.push_back(y); v.push_back(make_pair(make_pair(x,y),make_pair(-1,-1))); } while(off<2*n+m) off*=2; sort(v2.begin(),v2.end()); v2.erase(unique(v2.begin(),v2.end()),v2.end()); for(int i=0;i<n+m;i++) { int a=0; if(v[i].second.first==-1) a=m1[v[i].first]; v[i].first.first=lower_bound(v2.begin(),v2.end(),v[i].first.first)-v2.begin()+1; v[i].first.second=lower_bound(v2.begin(),v2.end(),v[i].first.second)-v2.begin()+1; if(a) m1[v[i].first]=a; if(v[i].second.first!=-1) { v[i].second.first=lower_bound(v2.begin(),v2.end(),v[i].second.first)-v2.begin()+1; v1[v[i].second.first+1].push_back(make_pair(v[i].first.second,v[i].second.second)); } if(v[i].second.second!=-1) v[i].second.second=lower_bound(v2.begin(),v2.end(),v[i].second.second)-v2.begin()+1; } v4=v; sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); /*cout << "\n"; for(int i=0;i<v.size();i++) { cout << v[i].first.first << " " << v[i].first.second << " " << v[i].second.first << " " << v[i].second.second << "\n"; } cout << "abc\n";*/ for(int i=1;i<=v2.size();i++) { //cout << int(t[10].size()) << "\n"; for(int j=0;j<v1[i].size();j++) { update(1,0,off-1,v1[i][j].first,v1[i][j].second,-1); } //cout << "def\n"; while(ind<v.size() && v[ind].first.first==i) { //cout << int(t[10].size()) << "\n"; if(v[ind].second.first==-1) { parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].first.second); v3[query(1,0,off-1,v[ind].first.second,v[ind].first.second)-1].push_back(ind); } else { parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].second.second); v3[query(1,0,off-1,v[ind].first.second,v[ind].second.second)-1].push_back(ind); //cout << int(t[10].size()) << "\n"; update(1,0,off-1,v[ind].first.second,v[ind].second.second,ind+1); } ind+=1; } } /*for(int i=0;i<v.size();i++) { cout << parent[i] << "\n"; } cout << "\n";*/ for(int i=0;i<v.size();i++) { if(parent[i]==-1) dfs(i); } for(int i=0;i<n;i++) { cout << cnt1[int(lower_bound(v.begin(),v.end(),v4[i])-v.begin())] << "\n"; //cout << "abc\n"; } //cout << "123\n"; /*for(int i=0;i<v.size();i++) { cout << parent[i] << " "; }*/ return 0; }

Compilation message (stderr)

plahte.cpp: In function 'std::set<int> dfs(int)':
plahte.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v3[x].size();i++) {
              ~^~~~~~~~~~~~~
plahte.cpp: In function 'void send(int)':
plahte.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p[x].size();i++) {
              ~^~~~~~~~~~~~
plahte.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p[x].size();i++) {
               ~^~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=v2.size();i++) {
              ~^~~~~~~~~~~
plahte.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v1[i].size();j++) {
               ~^~~~~~~~~~~~~
plahte.cpp:115:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<v.size() && v[ind].first.first==i) {
         ~~~^~~~~~~~~
plahte.cpp:134:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++) {
              ~^~~~~~~~~
plahte.cpp:67:16: warning: unused variable 'cnt' [-Wunused-variable]
  int n,m,ind=0,cnt=0;
                ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...