Submission #567773

#TimeUsernameProblemLanguageResultExecution timeMemory
567773errorgornTeam Contest (JOI22_team)C++17
0 / 100
81 ms15424 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ii pair<int,int> #define fi first #define se second #define endl '\n' #define puf push_front #define pof pop_front #define pub push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--) #define all(x) (x).begin(),(x).end() #define sz(x) (int) (x).size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct node{ const int BUF=150050; int arr[300100]; node(){ memset(arr,-1,sizeof(arr)); } void update(int i,int j){ i+=BUF; arr[i]=j; while (i){ i>>=1; arr[i]=max(arr[i<<1],arr[i<<1|1]); } } int query(int i,int j){ i+=BUF,j+=BUF+1; int res=-1; while (i<j){ if (i&1) res=max(res,arr[i++]); if (j&1) res=max(res,arr[--j]); i>>=1,j>>=1; } return res; } } root1,root2; int n; int arr[150005][3]; vector<int> uni[3]; ii best={-1,-1}; void add(int i,int j){ //cout<<"adding: "<<i<<" "<<j<<" "<<endl; root1.update(i,j); root2.update(j,i); int j2=root1.query(0,i-1); int i2=root2.query(0,j-1); if (j<j2) best=max(best,ii(i,j2)); if (i<i2) best=max(best,ii(i2,j)); } signed main(){ cin.tie(0); cout.tie(0); cin.sync_with_stdio(false); cin>>n; rep(x,0,n) rep(y,0,3) cin>>arr[x][y]; rep(x,0,n) rep(y,0,3) uni[y].pub(arr[x][y]); rep(x,0,3) sort(all(uni[x])); rep(x,0,n) rep(y,0,3) arr[x][y]=lb(all(uni[y]),arr[x][y])-uni[y].begin(); //rep(x,0,n){ //rep(y,0,3) cout<<arr[x][y]<<" "; cout<<endl; //} vector<int> idx; rep(x,0,n) idx.pub(x); sort(all(idx),[](int i,int j){ return arr[i][0]<arr[j][0]; }); int curr=0; int ans=-1; rep(x,0,n){ while (arr[idx[curr]][0]<arr[idx[x]][0]){ add(arr[idx[curr]][1],arr[idx[curr]][2]); curr++; } if (arr[idx[x]][1]<best.fi && arr[idx[x]][2]<best.se){ ans=max(ans,uni[0][arr[idx[x]][0]]+uni[1][best.fi]+uni[2][best.se]); } } cout<<ans<<endl; }
#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...