Submission #222725

#	Time	Username	Problem	Language	Result	Execution time	Memory
222725		kingfran1907	Tenis (COI19_tenis)	C++14	100 / 100	294 ms	7544 KiB

tenis

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;

const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, q;
int niz[3][maxn];
int pos[3][maxn];
int tour[treesiz];
int prop[treesiz];

void send(int node) {
    tour[node * 2] += prop[node];
    tour[node * 2 + 1] += prop[node];

    prop[node * 2] += prop[node];
    prop[node * 2 + 1] += prop[node];
    prop[node] = 0;
}

void update(int a, int b, int l, int r, int node, int val) {
    //printf("debug update: %d %d %d %d %d %d", a, b, l, r, node, val);
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
        tour[node] += val;
        prop[node] += val;
        return;
    }

    send(node);
    int mid = (l + r) / 2;
    update(a, b, l, mid, node * 2, val);
    update(a, b, mid + 1, r, node * 2 + 1, val);
    tour[node] = min(tour[node * 2], tour[node * 2 + 1]);
}

int query(int l, int r, int node) {
    if (l == r) return l;

    send(node);
    int mid = (l + r) / 2;
    if (tour[2 * node] == 0) return query(l, mid, node * 2);
    else return query(mid + 1, r, node * 2 + 1);
}

int cal(int x) {
    int maxi = -1;
    for (int i = 0; i < 3; i++)
        maxi = max(maxi, pos[i][x]);
    return maxi;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &niz[i][j]);

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < n; j++)
            pos[i][niz[i][j]] = j;

    for (int i = 0; i < n; i++)
        update(i, n - 1, 0, off - 1, 1, 1);

    for (int i = 1; i <= n; i++) {
        int maxi = -1;
        for (int j = 0; j < 3; j++)
            maxi = max(maxi, pos[j][i]);
        update(maxi, n - 1, 0, off - 1, 1, -1);
    }

    while (q--) {
        int type;
        scanf("%d", &type);

        if (type == 1) {
            int x;
            scanf("%d", &x);

            int ac = query(0, off - 1, 1);
            int tren = -1;
            for (int i = 0; i < 3; i++)
                tren = max(tren, pos[i][x]);

            if (tren <= ac) printf("DA\n");
            else printf("NE\n");
        } else {
            int p, a, b;
            scanf("%d%d%d", &p, &a, &b); p--;

            int pa = pos[p][a], pb = pos[p][b];
            swap(niz[p][pa], niz[p][pb]);

            update(cal(a), n - 1, 0, off - 1, 1, 1);
            update(cal(b), n - 1, 0, off - 1, 1, 1);
            swap(pos[p][a], pos[p][b]);
            update(cal(a), n - 1, 0, off - 1, 1, -1);
            update(cal(b), n - 1, 0, off - 1, 1, -1);
        }
    }
    return 0;
}

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:61: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:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &niz[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~
tenis.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &type);
         ~~~~~^~~~~~~~~~~~~
tenis.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
tenis.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &p, &a, &b); p--;
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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