Submission #499313

#TimeUsernameProblemLanguageResultExecution timeMemory
499313julian33Plahte (COCI17_plahte)C++14
0 / 160
1959 ms168652 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #ifdef LOCAL const int mxN=100; #else const int mxN=3e5+5; //make sure this is right #endif const int mod=1e9+7; struct RANK{ vector<int> all; int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;} void add(int x){all.pb(x);} void fix(){ sort(all.begin(),all.end()); all.resize(unique(all.begin(),all.end())-all.begin()); } } rnk; set<pii> st[4*mxN]; void update(int v,int l,int r,int ind,pii val,int t){ if(l>ind || r<ind) return; if(t) st[v].insert(val); else if(st[v].count(val)) st[v].erase(val); if(l==r) return; int m=(l+r)>>1; update(v<<1,l,m,ind,val,t); update(v<<1|1,m+1,r,ind,val,t); } pii query(int v,int l,int r,int lq,int rq,int lo,int hi){ // deb(l,r); if(lq>rq) return {-1,-1}; if(l>=lq && r<=rq){ // deb(sz(st[v]),l,r,lq,rq,lo,hi); if(!sz(st[v])) return {-1,-1}; if(st[v].rbegin()->first<lo) return {-1,-1}; if(st[v].begin()->first>hi) return {-1,-1}; return *st[v].lower_bound(pii(lo,hi)); } int m=(l+r)>>1; return max(query(v<<1,l,m,lq,min(rq,m),lo,hi),query(v<<1|1,m+1,r,max(lq,m+1),rq,lo,hi)); } struct rect{ ll a,b,c,d,i; }; struct paint{ int x,y,k; }; vector<int> graph[mxN]; set<int> col[mxN]; int ans[mxN]; void dfs(int at){ for(int &i:graph[at]){ dfs(i); if(sz(col[i])>sz(col[at])) swap(col[i],col[at]); for(int j:col[i]) col[at].insert(j); col[i].clear(); } ans[at]=sz(col[at]); } map<pii,vector<int>> mp; int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,m; cin>>n>>m; vector<rect> all,ori; vector<paint> off; for(int i=0;i<n;i++){ int a,b,c,d; cin>>a>>b>>c>>d; rnk.add(a); rnk.add(c); all.pb({a,b,c,d,i}); ori.pb({a,b,c,d,i}); } for(int i=0;i<m;i++){ int x,y,k; cin>>x>>y>>k; rnk.add(x); off.pb({x,y,k}); } rnk.fix(); sort(all.begin(),all.end(),[&](auto x,auto y){return (x.c-x.a)*(x.d-x.b)<(y.c-y.a)*(y.d-y.b);}); int N=sz(rnk.all); // assert(sz(rnk.all)<mxN); for(auto &[a,b,c,d,i]:all){ // deb(a,b,c,d,i); a=rnk.get(a); c=rnk.get(c); pii res; while(1){ res=query(1,1,N,a,c,b,d); if(res==pii(-1,-1)) break; // deb(res.first,res.second); graph[min(i,(ll)res.second)].pb(max(i,(ll)res.second)); update(1,1,N,rnk.get(ori[res.second].a),res,0); } update(1,1,N,a,{b,i},1); } for(int i=1;i<=4*N;i++) st[i].clear(); for(auto &[x,y,k]:off){ x=rnk.get(x); update(1,1,N,x,{y,k},1); mp[{y,k}].pb(x); } sort(all.begin(),all.end(),[&](auto x,auto y){return x.i>y.i;}); for(auto &[a,b,c,d,i]:all){ pii res; // deb(a,b,c,d,i); while(1){ res=query(1,1,N,a,c,b,d); if(res==pii(-1,-1)) break; // deb(res.first,res.second); if(sz(mp[res])){ col[i].insert(res.second); int x=mp[res].back(); mp[res].pop_back(); update(1,1,N,x,res,0); } else break; } } memset(ans,-1,sizeof(ans)); for(int i=0;i<n;i++){ if(ans[i]==-1) dfs(i); cout<<ans[i]<<"\n"; } }

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:124:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     for(auto &[a,b,c,d,i]:all){
      |               ^
plahte.cpp:140:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |     for(auto &[x,y,k]:off){
      |               ^
plahte.cpp:146:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |     for(auto &[a,b,c,d,i]:all){
      |               ^
#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...