oj.uz

Submission #714047

# Submission time Handle Problem Language Result Execution time Memory
714047 2023-03-23T17:29:03 Z Redhood Tenis (COI19_tenis) C++14
0 / 100
 138 ms 7856 KB 
#include <bits/stdc++.h>
 
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
//#define int long long
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e5+1;
int t[4*N],p[4*N];
void push(int v,int tl,int tr){
    if(tl==tr||!p[v])
        return;
    for(auto &u : {2*v,2*v+1})
        p[u]+=p[v],t[u]+=p[v];
    p[v]=0;
}
void add(int l,int r,int x,int v,int tl,int tr){
    if(tl>=l&&tr<=r){
        t[v]+=x;p[v]+=x;
        return;
    }
    if(tl>r||tr<l)
        return;
    int tm=(tl+tr)>>1;push(v,tl,tr);
    add(l,r,x,2*v,tl,tm);add(l,r,x,2*v+1,tm+1,tr);
    t[v]=min(t[2*v],t[2*v+1]);
}
int get(int l,int r,int v,int tl,int tr){
    if(tl>=l&&tr<=r)
        return t[v];
    if(tl>r||tr<l)
        return 1e9;
    int tm=(tl+tr)>>1;push(v,tl,tr);
    return min(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
}
signed main(){
    fast_prep;
    int n,q;
    cin>>n>>q;
    vec<vec<int>>p(3,vec<int>(n));
    vec<vec<int>>ord(3,vec<int>(n));
    for(int i=0;i<3;i++){
        for(auto &z : p[i])
            cin>>z,--z;
        for(int j=0;j<n;j++) ord[i][p[i][j]]=j;
    }
    for(int i=0;i<n;i++) add(0,i,1,1,0,n-1);
    auto eval=[&](int i){
        return max({ord[0][i],ord[1][i],ord[2][i]});
    };
    for(int i=0;i<n;i++){
        add(0,eval(i),-1,1,0,n-1);
    }
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int x;
            cin>>x;
            --x;
            int j=eval(x);
            cout<<(get(1,j,1,0,n-1)==0?"NE":"DA")<<'\n';
        }
        else{
            int k,i,j;
            cin>>k>>i>>j;--i;--j;--k;
            add(0,eval(i),1,1,0,n-1);add(0,eval(j),1,1,0,n-1);
            swap(ord[k][i],ord[k][j]);
            add(0,eval(i),-1,1,0,n-1);add(0,eval(j),-1,1,0,n-1);
 
        }
    }
    return 0;
}
/*
abbaaa
cbbbbccbbccbbbbbbc
(((((((()))())))))
 
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 7856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -