Submission #943758

#TimeUsernameProblemLanguageResultExecution timeMemory
943758amirhoseinfar1385The Potion of Great Power (CEOI20_potion)C++17
56 / 100
2398 ms126628 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=100000+10,maxd=40,maxq=50000+10; int te=0,n,d,high[maxn]; struct cmp { bool operator() (int a, int b) const { if(high[a]!=high[b]){ return high[a]<high[b]; } return a<b; } }; struct hams{ vector<int>timea; vector<vector<pair<int,int>>>allq; vector<set<int,cmp>>fi; set<int,cmp>st; hams(){ timea.resize(1,0); allq.resize(1); fi.push_back(st); } void ins(int u){ if(st.count(u)==1){ allq.back().push_back(make_pair(te,-u)); st.erase(u); }else{ allq.back().push_back(make_pair(te,u)); st.insert(u); } if((int)allq.back().size()==maxd){ timea.push_back(te); allq.push_back({}); fi.push_back(st); } } vector<int>pors(int w){ int p=upper_bound(timea.begin(),timea.end(),w)-timea.begin(); p--; set<int,cmp>fake=fi[p]; for(auto x:allq[p]){ if(x.first>w){ break; } if(x.second<0){ fake.erase(-x.second); }else{ fake.insert(x.second); } } vector<int>ret; for(auto x:fake){ ret.push_back(x); } return ret; } }alle[maxn]; void init(int N, int D, int H[]) { n=N; d=D; for(int i=0;i<n;i++){ high[i]=H[i]; } } void curseChanges(int U, int A[], int B[]) { for(int i=1;i<=U;i++){ te=i; alle[A[i-1]].ins(B[i-1]); alle[B[i-1]].ins(A[i-1]); } } bool cmp(int a,int b){ return high[a]<high[b]; } int question(int x, int y, int v) { vector<int>av=alle[x].pors(v); vector<int>dov=alle[y].pors(v); int i=0,j=0; int res=1000000000; while(i<(int)av.size()&&j<(int)dov.size()){ res=min(res,abs(high[av[i]]-high[dov[j]])); if(high[av[i]]==high[dov[j]]){ if(i+1==(int)av.size()){ j++; }else if(j+1==(int)dov.size()){ i++; }else if(high[av[i+1]]<high[dov[j+1]]){ i++; }else{ j++; } continue; } if(high[av[i]]<high[dov[j]]){ i++; }else{ j++; } } return res; }
#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...