Submission #769782

#	Time	Username	Problem	Language	Result	Execution time	Memory
769782		bgnbvnbv	Tenis (COI19_tenis)	C++14	100 / 100	145 ms	9916 KiB

tenis

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll lazy[4*maxN],st[4*maxN];
void down(ll id)
{
    ll &x=lazy[id];
    st[id*2]+=x;
    lazy[id*2]+=x;
    st[id*2+1]+=x;
    lazy[id*2+1]+=x;
    x=0;
}
ll n;
void update(ll i,ll j,ll v,ll id=1,ll l=2,ll r=n)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]+=v;
        lazy[id]+=v;
        return;
    }
    ll mid=l+r>>1;
    down(id);
    update(i,j,v,id*2,l,mid);
    update(i,j,v,id*2+1,mid+1,r);
    st[id]=min(st[id*2],st[id*2+1]);
}
ll get()
{
    ll id=1,l=2,r=n;
    if(st[1]>0) return n+1;
    while(true)
    {
        if(l==r) return l;
        ll mid=l+r>>1;
        down(id);
        if(st[id*2]>0)
        {
            id=id*2+1;
            l=mid+1;
        }
        else
        {
            id=id*2;
            r=mid;
        }
    }
}
ll q;
ll pos[5][maxN];
ll gt(ll i)
{
    ll cc=n+1;
    for(int j=1;j<=3;j++)
    {
        cc=min(cc,pos[j][i]);
    }
    return cc;
}
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=3;i++)
    {
        ll x;
        for(int j=1;j<=n;j++) cin >> x,pos[i][x]=j;
    }
    for(int i=n;i>=2;i--)
    {
        update(2,i,1);
        ll cc=n+1;
    }
    for(int i=1;i<=n;i++)
    {
        ll cc=gt(i);
        update(2,cc,-1);
    }
    for(int i=1;i<=q;i++)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll x;
            cin >> x;
            ll vd=get();
            ll cc=gt(x);
            if(vd<=cc) cout <<"NE\n";
            else cout <<"DA\n";
        }
        else
        {
            ll j,x,y;
            cin >> j >> x >> y;
            ll cc=gt(x);
            update(2,cc,1);
            cc=gt(y);
            update(2,cc,1);
            swap(pos[j][x],pos[j][y]);
            cc=gt(x);
            update(2,cc,-1);
            cc=gt(y);
            update(2,cc,-1);
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

tenis.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
tenis.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     ll mid=l+r>>1;
      |            ~^~
tenis.cpp: In function 'll get()':
tenis.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         ll mid=l+r>>1;
      |                ~^~
tenis.cpp: In function 'void solve()':
tenis.cpp:82:12: warning: unused variable 'cc' [-Wunused-variable]
   82 |         ll cc=n+1;
      |            ^~

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