Submission #57907

#	Time	Username	Problem	Language	Result	Execution time	Memory
57907		choikiwon	Employment (JOI16_employment)	C++17	100 / 100	1240 ms	112092 KiB

employment

#include<bits/stdc++.h>
using namespace std;

const int MN = 200010;

int N, M;
int A[MN];
struct Query {
    int t, x, y;
};
Query query[MN];

int Xn;
vector<int> X;
map<int, int> dx;

vector<int> V[MN << 1];
int chk[MN << 1], ans[MN << 1];

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * Xn, 0);
    }
    void upd(int a, int b, int d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            return;
        }
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
    }
    int quer(int idx, int l, int r, int n) {
        if(idx < l || r < idx) return 0;
        int ret = tree[n];
        if(l == r) return ret;
        int m = (l + r)>>1;
        int L = quer(idx, l, m, 2*n);
        int R = quer(idx, m + 1, r, 2*n + 1);
        return ret + L + R;
    }
} bit;

void rem(int idx, int val) {
    int cnt = 1;
    if(idx && A[idx - 1] >= val) cnt--;
    if(idx < N - 1 && A[idx + 1] >= val) cnt--;
    bit.upd(0, val, -cnt, 0, Xn - 1, 1);

    if(idx && A[idx - 1] < val) {
        bit.upd(0, A[idx - 1], 1, 0, Xn - 1, 1);
    }
    if(idx < N - 1 && A[idx + 1] < val) {
        bit.upd(0, A[idx + 1], 1, 0, Xn - 1, 1);
    }
}
void add(int idx, int val) {
    int cnt = 1;
    if(idx && A[idx - 1] >= val) cnt--;
    if(idx < N - 1 && A[idx + 1] >= val) cnt--;
    bit.upd(0, val, cnt, 0, Xn - 1, 1);

    if(idx && A[idx - 1] < val) {
        bit.upd(0, A[idx - 1], -1, 0, Xn - 1, 1);
    }
    if(idx < N - 1 && A[idx + 1] < val) {
        bit.upd(0, A[idx + 1], -1, 0, Xn - 1, 1);
    }
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        X.push_back(A[i]);
    }
    for(int i = 0; i < M; i++) {
        int t; scanf("%d", &t);

        if(t == 1) {
            int x; scanf("%d", &x);
            query[i] = {t, x, -1};
            X.push_back(x);
        }
        if(t == 2) {
            int c, d; scanf("%d %d", &c, &d);
            c--;
            query[i] = {t, c, d};
            X.push_back(d);
        }
    }

    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());
    Xn = X.size();
    for(int i = 0; i < Xn; i++) dx[X[i]] = i;
    for(int i = 0; i < N; i++) {
        A[i] = dx[A[i]];
    }
    for(int i = 0; i < M; i++) {
        if(query[i].t == 1) {
            query[i].x = dx[ query[i].x ];
        }
        if(query[i].t == 2) {
            query[i].y = dx[ query[i].y ];
        }
    }
    for(int i = 0; i < N; i++) {
        V[ A[i] ].push_back(i);
    }
    int cnt = 0;
    for(int i = Xn - 1; i >= 0; i--) {
        for(int j = 0; j < V[i].size(); j++) {
            cnt++;
            if(V[i][j] > 0 && chk[ V[i][j] - 1 ]) cnt--;
            if(chk[ V[i][j] + 1 ]) cnt--;
            chk[ V[i][j] ] = 1;
        }
        ans[i] = cnt;
    }

    bit.init();
    for(int i = 0; i < M; i++) {
        int t = query[i].t;
        int x = query[i].x;
        int y = query[i].y;

        if(t == 1) {
            printf("%d\n", ans[x] + bit.quer(x, 0, Xn - 1, 1));
        }
        if(t == 2) {
            int z = A[x];

            rem(x, z);
            add(x, y);

            A[x] = y;
        }
    }
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:116:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < V[i].size(); j++) {
                        ~~^~~~~~~~~~~~~
employment.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
employment.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
employment.cpp:81:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t; scanf("%d", &t);
                ~~~~~^~~~~~~~~~
employment.cpp:84:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int x; scanf("%d", &x);
                    ~~~~~^~~~~~~~~~
employment.cpp:89:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int c, d; scanf("%d %d", &c, &d);
                       ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60