제출 #1244135

#제출 시각아이디문제언어결과실행 시간메모리
1244135ereringTeam Contest (JOI22_team)C++20
18 / 100
2092 ms37996 KiB
#include <bits/stdc++.h> #define pb push_back //#define int long long #define endl '\n' using namespace std; const int N=2e5+5,inf=2e8,MOD=1e9+9; struct node{ node* l=NULL; node* r=NULL; node* seg=NULL; int mx=-inf; }; node* root=new node; node* root2=new node; node* rooty=new node; node* rootz=new node; int offset=1; const int MXV=4000+5; int flag2=0; void update(node* cur,int idx,int lo,int hi,int val){ if(lo>idx || hi<idx)return; if(lo==idx && hi==idx){ cur->mx=max(cur->mx,val); return; } int mid=(lo+hi)/2; if(cur->l==NULL)cur->l=new node; if(cur->r==NULL)cur->r=new node; update(cur->l,idx,lo,mid,val); update(cur->r,idx,mid+1,hi,val); cur->mx=max({cur->mx,cur->l->mx,cur->r->mx}); } int query2(node* cur,int qlo,int qhi,int lo,int hi){ if(lo>=qlo && hi<=qhi)return cur->mx; if(lo>qhi || hi<qlo)return -inf; int mx=-inf,mid=(lo+hi)/2; if(cur->l!=NULL)mx=max(mx,query2(cur->l,qlo,qhi,lo,mid)); if(cur->r!=NULL)mx=max(mx,query2(cur->r,qlo,qhi,mid+1,hi)); return mx; } int query(node* cur,int qlo,int qhi,int lo,int hi,int z){ if(lo>=qlo && hi<=qhi){ if(cur->seg==NULL)return -inf; return query2(cur->seg,z+1,MXV,0,offset-1); } if(lo>qhi || hi<qlo)return -inf; if(cur->l==NULL)cur->l=new node; if(cur->r==NULL)cur->r=new node; int mx=-inf,mid=(lo+hi)/2; if(cur->l!=NULL)mx=max(mx,query(cur->l,qlo,qhi,lo,mid,z)); if(cur->r!=NULL)mx=max(mx,query(cur->r,qlo,qhi,mid+1,hi,z)); return mx; } int uglytask; void insert(node* cur,int idx,int lo,int hi,int val){ if(lo>idx || hi<idx)return; if(lo==idx && hi==idx){ if(cur->seg==NULL)cur->seg=new node; int z; if(!flag2)z=query(rooty,0,idx-1,0,offset-1,val); else if(flag2==1)z=query(rootz,0,idx-1,0,offset-1,val); else{ uglytask=-1; update(cur->seg,val,0,offset-1,val); return; } uglytask=z; update(cur->seg,z,0,offset-1,idx+z); return; } int mid=(lo+hi)/2; if(cur->l==NULL)cur->l=new node; if(cur->r==NULL)cur->r=new node; insert(cur->l,idx,lo,mid,val); insert(cur->r,idx,mid+1,hi,val); int a=-inf,b=-inf; if(cur->seg==NULL)cur->seg=new node; if(uglytask!=-1)val=uglytask; int v=query2(cur->seg,val,val,0,offset-1); if(idx>=lo && idx<=mid){ a=query2(cur->l->seg,val,val,0,offset-1); } else b=query2(cur->r->seg,val,val,0,offset-1); update(cur->seg,val,0,offset-1,max({v,a,b})); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; while(offset<MXV)offset*=2; int ans=-1; pair<int,pair<int,int>> p[n]; for(int i=0;i<n;i++){ int x,y,z; cin>>x>>y>>z; p[i]={x,{y,z}}; int sol; sol=query(root,y+1,MXV-5,0,offset-1,z); sol=max(sol,query(root2,z+1,MXV-5,0,offset-1,y)); sol+=x; ans=max(ans,sol); } sort(p,p+n); for(int i=0;i<n;i++){ int x=p[i].first,y,z; if(i>0 && x!=p[i-1].first){ for(int j=i-1;j>=0;j--){ if(j!=i-1 && p[j].first!=p[j+1].first)break; y=p[j].second.first; z=p[j].second.second; flag2=0; insert(root,y,0,offset-1,z); flag2=1; insert(root2,z,0,offset-1,y); flag2=2; insert(rooty,y,0,offset-1,z); insert(rootz,z,0,offset-1,y); } } y=p[i].second.first; z=p[i].second.second; int sol; sol=query(root,y+1,MXV-5,0,offset-1,z); sol=max(sol,query(root2,z+1,MXV-5,0,offset-1,y)); sol+=x; ans=max(ans,sol); } cout<<ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...