Submission #175995

#TimeUsernameProblemLanguageResultExecution timeMemory
175995nikolapesic2802Tenis (COI19_tenis)C++14
30 / 100
783 ms88692 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll long long #define pb push_back #define sz(x) (int)(x).size() #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() #define D(x) cerr << #x << " is " << (x) << "\n"; #define ld long double using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key() template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} const int N=1e5+5; vector<vector<int> > arr(3,vector<int>(N)),pos(3,vector<int>(N)),last(3,vector<int>(N)),vals(3,vector<int>(N,-1)); vector<vector<tuple<int,int,int> > > dodaj(4*N); void add(int qs,int qe,tuple<int,int,int> x,int l=0,int r=N-1,int i=1){ /*if(i==1) printf("%i-%i %i %i %i\n",qs,qe,get<0>(x),get<1>(x),get<2>(x));*/ if(qs>r||qe<l) return; if(qs<=l&&qe>=r){ dodaj[i].pb(x); return; } int m=(l+r)>>1; add(qs,qe,x,l,m,2*i); add(qs,qe,x,m+1,r,2*i+1); } int tr=0; vector<int> queries(N); vector<int> reach(N); int trReach=0; vector<vector<pair<int,pair<int,int> > > > undo; vector<pair<int,pair<int,int> > > em; void sett(int p,int a,int ind){ vals[p][a]=ind; undo.pb(em); undo.back().pb({0,{p,a}}); if(vals[0][a]!=-1&&vals[1][a]!=-1&&vals[2][a]!=-1){ int mi=min({vals[0][a],vals[1][a],vals[2][a]}),ma=max({vals[0][a],vals[1][a],vals[2][a]}); if(mi<=trReach){ int newReach=ma; for(int i=trReach+1;i<=newReach;i++) newReach=max(newReach,reach[i]); if(newReach>trReach){ undo.back().pb({1,{trReach,trReach}}); trReach=newReach; } }else{ if(reach[mi]<ma) undo.back().pb({2,{mi,reach[mi]}}),reach[mi]=ma; } } } void undo_it(){ for(auto p:undo.back()){ if(p.f==0) vals[p.s.f][p.s.s]=-1; if(p.f==1) trReach=p.s.f; if(p.f==2) reach[p.s.f]=p.s.s; } undo.pop_back(); } void solve(int l=0,int r=N-1,int i=1){ if(l>=tr) return; for(auto p:dodaj[i]) sett(get<0>(p),get<1>(p),get<2>(p)); if(l==r){ int index=vals[0][queries[l]]; if(index<=trReach) printf("DA\n"); else printf("NE\n"); for(auto p:dodaj[i]) undo_it(); return; } int m=(l+r)>>1; solve(l,m,2*i); solve(m+1,r,2*i+1); for(auto p:dodaj[i]) undo_it(); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,q; scanf("%i %i",&n,&q); for(int i=0;i<3;i++) for(int j=0;j<n;j++) scanf("%i",&arr[i][j]),arr[i][j]--,pos[i][arr[i][j]]=j; vector<pair<pair<int,int>,tuple<int,int,int> > > ad; for(int i=0;i<q;i++){ int t; scanf("%i",&t); if(t==1){ int x; scanf("%i",&x); queries[tr++]=x-1; }else{ int p,a,b; scanf("%i %i %i",&p,&a,&b); p--;a--;b--; if(last[p][a]!=tr) add(last[p][a],tr-1,make_tuple(p,a,pos[p][a])); if(last[p][b]!=tr) add(last[p][b],tr-1,make_tuple(p,b,pos[p][b])); last[p][b]=last[p][a]=tr; swap(arr[p][pos[p][a]],arr[p][pos[p][b]]); swap(pos[p][a],pos[p][b]); } } for(int i=0;i<3;i++) for(int j=0;j<n;j++) if(last[i][j]!=tr) add(last[i][j],tr-1,make_tuple(i,j,pos[i][j])); solve(); return 0; }

Compilation message (stderr)

tenis.cpp: In function 'void solve(int, int, int)':
tenis.cpp:95:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
         for(auto p:dodaj[i])
                  ^
tenis.cpp:102:14: warning: variable 'p' set but not used [-Wunused-but-set-variable]
     for(auto p:dodaj[i])
              ^
tenis.cpp: In function 'int main()':
tenis.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
tenis.cpp:113:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&arr[i][j]),arr[i][j]--,pos[i][arr[i][j]]=j;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
tenis.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
tenis.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&x);
             ~~~~~^~~~~~~~~
tenis.cpp:124:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i %i %i",&p,&a,&b);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...