Submission #175996

#	Time	Username	Problem	Language	Result	Execution time	Memory
175996		nikolapesic2802	Tenis (COI19_tenis)	C++14	100 / 100	369 ms	55644 KiB

tenis

#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,int r,int i){
    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,int r,int i){
    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)
                ad.pb({{last[p][a],tr-1},make_tuple(p,a,pos[p][a])});
            if(last[p][b]!=tr)
                ad.pb({{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(auto p:ad)
        add(p.f.f,p.f.s,p.s,0,tr-1,1);
    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]),0,tr-1,1);
    solve(0,tr-1,1);
    return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'void solve(int, int, int)':
tenis.cpp:93:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
         for(auto p:dodaj[i])
                  ^
tenis.cpp:100: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:108: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:111: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:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
tenis.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&x);
             ~~~~~^~~~~~~~~
tenis.cpp:122: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);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49