Submission #448693

#	Time	Username	Problem	Language	Result	Execution time	Memory
448693		MOUF_MAHMALAT	Tenis (COI19_tenis)	C++14	100 / 100	317 ms	4112 KiB

tenis

#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,q,a[100009][3],x,y,t,o,u;
ll p[400009],lz[400009];
void push(ll d,ll l,ll r)
{
    p[d]+=lz[d];
    if(l<r)
    {
        lz[d*2]+=lz[d];
        lz[d*2+1]+=lz[d];
    }
    lz[d]=0;
}
void up(ll d,ll l,ll r,ll z)
{
    push(d,l,r);
    if(r<x||l>y)
        return;
    if(x<=l&&y>=r)
    {
        lz[d]+=z;
        push(d,l,r);
        return;
    }
    ll m=(l+r)/2,i=d*2;
    up(i,l,m,z),up(i+1,m+1,r,z);
    p[d]=min(p[i],p[i+1]);
}
ll best(ll d,ll l,ll r)
{
    if(l>y)
        return 1e9;
    push(d,l,r);
    if(r<=y)
        return p[d];
    ll m=(l+r)/2,i=d*2;
    return min(best(i,l,m),best(i+1,m+1,r));
}
int main()
{
    scanf("%d%d",&n,&q);
    for(ll j=0; j<3; j++)
        for(ll i=1; i<=n; i++)
        {
            scanf("%d",&x);
            a[x][j]=i;
        }
    for(ll i=1; i<=n; i++)
    {
        x=min(a[i][0],min(a[i][1],a[i][2]));
        y=max(a[i][0],max(a[i][1],a[i][2]))-1;
        up(1,1,n,1);
    }
    while(q--)
    {
        scanf("%d",&t);
        if(t==1)
        {
            scanf("%d",&x);
            y=min(a[x][0],min(a[x][1],a[x][2]))-1;
            if(best(1,1,n))
                printf("DA\n");
            else
                printf("NE\n");
            continue;
        }
        scanf("%d%d%d",&t,&o,&u),t--;
        x=min(a[o][0],min(a[o][1],a[o][2]));
        y=max(a[o][0],max(a[o][1],a[o][2]))-1;
        up(1,1,n,-1);
        x=min(a[u][0],min(a[u][1],a[u][2]));
        y=max(a[u][0],max(a[u][1],a[u][2]))-1;
        up(1,1,n,-1);

        swap(a[o][t],a[u][t]);
        x=min(a[o][0],min(a[o][1],a[o][2]));
        y=max(a[o][0],max(a[o][1],a[o][2]))-1;
        up(1,1,n,1);
        x=min(a[u][0],min(a[u][1],a[u][2]));
        y=max(a[u][0],max(a[u][1],a[u][2]))-1;
        up(1,1,n,1);
    }
    return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
tenis.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
tenis.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
tenis.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
tenis.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d%d%d",&t,&o,&u),t--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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