oj.uz

답안 #175994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
175994 2020-01-07T13:59:14 Z nikolapesic2802 Tenis (COI19_tenis) C++14
100 / 100
 380 ms 58716 KB 
#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){
    //printf("%i %i %i\n",p,a,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;
    //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]];
        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])});
                //add(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])});
                //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(auto p:ad)
        add(p.f.f,p.f.s,p.s,0,tr-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);
    solve(0,tr-1,1);
    return 0;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15216 KB Output is correct
2 Correct 15 ms 15216 KB Output is correct
3 Correct 16 ms 15216 KB Output is correct
4 Correct 19 ms 15264 KB Output is correct
5 Correct 16 ms 15216 KB Output is correct
6 Correct 8 ms 15216 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15216 KB Output is correct
2 Correct 15 ms 15216 KB Output is correct
3 Correct 16 ms 15216 KB Output is correct
4 Correct 19 ms 15264 KB Output is correct
5 Correct 16 ms 15216 KB Output is correct
6 Correct 8 ms 15216 KB Output is correct
7 Correct 16 ms 15468 KB Output is correct
8 Correct 16 ms 15472 KB Output is correct
9 Correct 16 ms 15472 KB Output is correct
10 Correct 16 ms 15468 KB Output is correct
11 Correct 18 ms 15472 KB Output is correct
12 Correct 20 ms 15472 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15216 KB Output is correct
2 Correct 15 ms 15216 KB Output is correct
3 Correct 16 ms 15216 KB Output is correct
4 Correct 19 ms 15264 KB Output is correct
5 Correct 16 ms 15216 KB Output is correct
6 Correct 8 ms 15216 KB Output is correct
7 Correct 16 ms 15468 KB Output is correct
8 Correct 16 ms 15472 KB Output is correct
9 Correct 16 ms 15472 KB Output is correct
10 Correct 16 ms 15468 KB Output is correct
11 Correct 18 ms 15472 KB Output is correct
12 Correct 20 ms 15472 KB Output is correct
13 Correct 126 ms 39260 KB Output is correct
14 Correct 130 ms 39212 KB Output is correct
15 Correct 125 ms 39204 KB Output is correct
16 Correct 124 ms 39284 KB Output is correct
17 Correct 125 ms 39332 KB Output is correct
18 Correct 126 ms 39332 KB Output is correct
19 Correct 124 ms 39256 KB Output is correct
20 Correct 65 ms 15144 KB Output is correct
21 Correct 126 ms 39364 KB Output is correct
22 Correct 125 ms 39280 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 39216 KB Output is correct
2 Correct 163 ms 39200 KB Output is correct
3 Correct 163 ms 39372 KB Output is correct
4 Correct 161 ms 39264 KB Output is correct
5 Correct 160 ms 39224 KB Output is correct
6 Correct 159 ms 39232 KB Output is correct
7 Correct 162 ms 39240 KB Output is correct
8 Correct 160 ms 39256 KB Output is correct
9 Correct 160 ms 39304 KB Output is correct
10 Correct 158 ms 39220 KB Output is correct
11 Correct 161 ms 39408 KB Output is correct
12 Correct 161 ms 39292 KB Output is correct
13 Correct 159 ms 39260 KB Output is correct
14 Correct 163 ms 39188 KB Output is correct
15 Correct 163 ms 39296 KB Output is correct

Subtask #5
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 15216 KB Output is correct
2 Correct 15 ms 15216 KB Output is correct
3 Correct 16 ms 15216 KB Output is correct
4 Correct 19 ms 15264 KB Output is correct
5 Correct 16 ms 15216 KB Output is correct
6 Correct 8 ms 15216 KB Output is correct
7 Correct 16 ms 15468 KB Output is correct
8 Correct 16 ms 15472 KB Output is correct
9 Correct 16 ms 15472 KB Output is correct
10 Correct 16 ms 15468 KB Output is correct
11 Correct 18 ms 15472 KB Output is correct
12 Correct 20 ms 15472 KB Output is correct
13 Correct 126 ms 39260 KB Output is correct
14 Correct 130 ms 39212 KB Output is correct
15 Correct 125 ms 39204 KB Output is correct
16 Correct 124 ms 39284 KB Output is correct
17 Correct 125 ms 39332 KB Output is correct
18 Correct 126 ms 39332 KB Output is correct
19 Correct 124 ms 39256 KB Output is correct
20 Correct 65 ms 15144 KB Output is correct
21 Correct 126 ms 39364 KB Output is correct
22 Correct 125 ms 39280 KB Output is correct
23 Correct 165 ms 39216 KB Output is correct
24 Correct 163 ms 39200 KB Output is correct
25 Correct 163 ms 39372 KB Output is correct
26 Correct 161 ms 39264 KB Output is correct
27 Correct 160 ms 39224 KB Output is correct
28 Correct 159 ms 39232 KB Output is correct
29 Correct 162 ms 39240 KB Output is correct
30 Correct 160 ms 39256 KB Output is correct
31 Correct 160 ms 39304 KB Output is correct
32 Correct 158 ms 39220 KB Output is correct
33 Correct 161 ms 39408 KB Output is correct
34 Correct 161 ms 39292 KB Output is correct
35 Correct 159 ms 39260 KB Output is correct
36 Correct 163 ms 39188 KB Output is correct
37 Correct 163 ms 39296 KB Output is correct
38 Correct 363 ms 54880 KB Output is correct
39 Correct 214 ms 46680 KB Output is correct
40 Correct 361 ms 58716 KB Output is correct
41 Correct 243 ms 49116 KB Output is correct
42 Correct 252 ms 49760 KB Output is correct
43 Correct 370 ms 56408 KB Output is correct
44 Correct 216 ms 46684 KB Output is correct
45 Correct 261 ms 50756 KB Output is correct
46 Correct 223 ms 47040 KB Output is correct
47 Correct 244 ms 49448 KB Output is correct
48 Correct 225 ms 47576 KB Output is correct
49 Correct 265 ms 49120 KB Output is correct
50 Correct 214 ms 46296 KB Output is correct
51 Correct 260 ms 49888 KB Output is correct
52 Correct 380 ms 58280 KB Output is correct
53 Correct 263 ms 47268 KB Output is correct
54 Correct 233 ms 48192 KB Output is correct
55 Correct 255 ms 50360 KB Output is correct
56 Correct 261 ms 49400 KB Output is correct
57 Correct 223 ms 47064 KB Output is correct
58 Correct 347 ms 58080 KB Output is correct