Submission #186835

#	Time	Username	Problem	Language	Result	Execution time	Memory
186835		anonymous	Tenis (COI19_tenis)	C++14	100 / 100	180 ms	7916 KiB

tenis

#include<iostream>
#define MAXN 100005
using namespace std;
int N,Q, L[MAXN][3], Pos[MAXN][3]; //(i,j,k) lowest ranked player on court type i in first k of court type j
bool done[MAXN];
int op, qa, qb, qc;
/* The critical observation is that the people who can win tournament occupy a prefix
of the rankings in each of the 3 court type. Otherwise, if l<=x<=r in a court type
and l, r can win then x can win also. Hence we want to find a ranking P
that the first P people in each of the 3 court types are same. This is done with segment tree*/
class Segtree {
    int ST[MAXN*4][2]; //sum, prefix max
    void pushup(int cur) {
        ST[cur][0]=ST[2*cur][0]+ST[2*cur+1][0];
        ST[cur][1]=max(ST[2*cur][1], ST[2*cur][0]+ST[2*cur+1][1]);
    }
public:
    void build(int l, int r, int cur) {
        if (l == r) {
            ST[cur][0]=ST[cur][1]=-1;
        } else {
            int mid=(l+r)>>1;
            build(l, mid, 2*cur);
            build(mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    void upd(int ind, int val, int l, int r, int cur) {
        if (l > ind || ind > r) {return;}
        if (l == r) {
            ST[cur][0]+=val, ST[cur][1]+=val;
        } else {
            int mid=(l+r)>>1;
            upd(ind, val, l, mid, 2*cur);
            upd(ind, val, mid+1, r, 2*cur+1);
            pushup(cur);
        }
    }
    int Find(int s, int l, int r, int cur) {
        if (l == r) {return(l);}
        else {
            int mid=(l+r)>>1;
            if (ST[2*cur][1] + s < 0) {
                return(Find(s+ST[2*cur][0], mid+1,r, 2*cur+1));
            } else {
                return(Find(s, l, mid, 2*cur));
            }
        }
    }
} ST;
int worst(int p) {
    return(max(Pos[p][0], max(Pos[p][1], Pos[p][2])));
}
bool ask(int x) {
    return(worst(x) <= ST.Find(0, 1, N, 1));
}
int main() {
    //freopen("tenin.txt","r",stdin);
    scanf("%d %d",&N,&Q);
    for (int i=0; i<3; i++) {
        for (int j=1; j<=N; j++) {
            scanf("%d", &L[j][i]);
        }
    }

    ST.build(1, N, 1);
    for (int i=0; i<3; i++) {
        for (int j=1; j<=N; j++) {
            Pos[L[j][i]][i]=j;
        }
    }
    for (int i=1; i<=N; i++) {
        ST.upd(worst(i), 1, 1, N, 1);
    }

    for (int i=0; i<Q; i++) {
        scanf("%d", &op);
        if (op == 2) {
            scanf("%d %d %d", &qa, &qb, &qc);
            ST.upd(worst(qb), -1, 1, N, 1);
            ST.upd(worst(qc), -1, 1, N, 1);
            swap(L[Pos[qb][qa-1]][qa-1], L[Pos[qc][qa-1]][qa-1]);
            swap(Pos[qb][qa-1], Pos[qc][qa-1]);
            ST.upd(worst(qb), 1, 1, N, 1);
            ST.upd(worst(qc), 1, 1, N, 1);
        } else {
            scanf("%d", &qa);
            printf("%s\n", ask(qa) ? "DA" : "NE");
        }
    }
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&Q);
     ~~~~~^~~~~~~~~~~~~~~
tenis.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &L[j][i]);
             ~~~~~^~~~~~~~~~~~~~~~
tenis.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &op);
         ~~~~~^~~~~~~~~~~
tenis.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &qa, &qb, &qc);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tenis.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &qa);
             ~~~~~^~~~~~~~~~~

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