oj.uz

Submission #57902

# Submission time Handle Problem Language Result Execution time Memory
57902 2018-07-16T13:44:48 Z choikiwon Employment (JOI16_employment) C++17
30 / 100
 1173 ms 103564 KB 
#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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9960 KB Output is correct
2 Correct 16 ms 10312 KB Output is correct
3 Correct 15 ms 10504 KB Output is correct
4 Correct 64 ms 13448 KB Output is correct
5 Correct 105 ms 17548 KB Output is correct
6 Correct 220 ms 21476 KB Output is correct
7 Correct 345 ms 28660 KB Output is correct
8 Correct 355 ms 34224 KB Output is correct
9 Correct 708 ms 48280 KB Output is correct
10 Correct 574 ms 51908 KB Output is correct
11 Correct 854 ms 60556 KB Output is correct
12 Correct 1079 ms 68940 KB Output is correct
13 Correct 1069 ms 73452 KB Output is correct
14 Correct 821 ms 76692 KB Output is correct
15 Correct 1086 ms 81044 KB Output is correct
16 Correct 1077 ms 86284 KB Output is correct
17 Correct 1075 ms 90848 KB Output is correct
18 Correct 1173 ms 94996 KB Output is correct
19 Correct 927 ms 99140 KB Output is correct
20 Correct 1072 ms 103564 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -