Submission #175987

#TimeUsernameProblemLanguageResultExecution timeMemory
175987nikolapesic2802Tenis (COI19_tenis)C++14
0 / 100
34 ms29820 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); set<int> intervals; vector<vector<pair<int,int> > > undo; vector<pair<int,int> > em; void sett(int p,int a,int ind){ //printf("%i %i %i\n",p,a,ind); vals[p][a]=ind; undo.pb(em); undo.back().pb({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]}); //printf("%i: %i %i!!\n",a,mi,ma); auto it=intervals.upper_bound(mi); while(it!=intervals.end()&&(*it)<=ma) undo.back().pb({-1,*it}),intervals.erase(it),it=intervals.upper_bound(mi); } } void undo_it(){ for(auto p:undo.back()) if(p.f==-1) intervals.insert(p.s); else vals[p.f][p.s]=-1; undo.pop_back(); } void solve(int l=0,int r=N-1,int i=1){ if(l>=tr) return; //printf("%i-%i!!\n",l,r); for(auto p:dodaj[i]) sett(get<0>(p),get<1>(p),get<2>(p)); if(l==r){ int index=vals[0][queries[l]]; //cout << intervals << endl; auto tr=*intervals.begin(); if(index<tr) 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; 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])); for(int i=1;i<=n;i++) intervals.insert(i); solve(); return 0; }

Compilation message (stderr)

tenis.cpp: In function 'void solve(int, int, int)':
tenis.cpp:87:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
         for(auto p:dodaj[i])
                  ^
tenis.cpp:94: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:99:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("in.txt","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
tenis.cpp:102: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:105: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:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
tenis.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&x);
             ~~~~~^~~~~~~~~
tenis.cpp:115: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...