답안 #57907 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57907	2018-07-16T13:46:45 Z	choikiwon	Employment (JOI16_employment)	C++17	100 / 100	1240 ms	112092 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Output is correct
2	Correct	11 ms	9836 KB	Output is correct
3	Correct	14 ms	9928 KB	Output is correct
4	Correct	13 ms	10248 KB	Output is correct
5	Correct	13 ms	10248 KB	Output is correct
6	Correct	13 ms	10248 KB	Output is correct
7	Correct	14 ms	10288 KB	Output is correct
8	Correct	17 ms	10444 KB	Output is correct
9	Correct	21 ms	10444 KB	Output is correct
10	Correct	15 ms	10592 KB	Output is correct
11	Correct	16 ms	10592 KB	Output is correct
12	Correct	16 ms	10652 KB	Output is correct
13	Correct	15 ms	10672 KB	Output is correct
14	Correct	16 ms	10720 KB	Output is correct
15	Correct	15 ms	10792 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10792 KB	Output is correct
2	Correct	17 ms	10964 KB	Output is correct
3	Correct	18 ms	11116 KB	Output is correct
4	Correct	63 ms	13896 KB	Output is correct
5	Correct	111 ms	17940 KB	Output is correct
6	Correct	167 ms	21444 KB	Output is correct
7	Correct	250 ms	27048 KB	Output is correct
8	Correct	317 ms	30616 KB	Output is correct
9	Correct	700 ms	41376 KB	Output is correct
10	Correct	590 ms	42016 KB	Output is correct
11	Correct	799 ms	46748 KB	Output is correct
12	Correct	941 ms	51104 KB	Output is correct
13	Correct	903 ms	51428 KB	Output is correct
14	Correct	879 ms	51428 KB	Output is correct
15	Correct	891 ms	51428 KB	Output is correct
16	Correct	877 ms	51872 KB	Output is correct
17	Correct	1034 ms	51872 KB	Output is correct
18	Correct	1099 ms	51872 KB	Output is correct
19	Correct	903 ms	51872 KB	Output is correct
20	Correct	891 ms	51872 KB	Output is correct

Subtask #3
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9720 KB	Output is correct
2	Correct	11 ms	9836 KB	Output is correct
3	Correct	14 ms	9928 KB	Output is correct
4	Correct	13 ms	10248 KB	Output is correct
5	Correct	13 ms	10248 KB	Output is correct
6	Correct	13 ms	10248 KB	Output is correct
7	Correct	14 ms	10288 KB	Output is correct
8	Correct	17 ms	10444 KB	Output is correct
9	Correct	21 ms	10444 KB	Output is correct
10	Correct	15 ms	10592 KB	Output is correct
11	Correct	16 ms	10592 KB	Output is correct
12	Correct	16 ms	10652 KB	Output is correct
13	Correct	15 ms	10672 KB	Output is correct
14	Correct	16 ms	10720 KB	Output is correct
15	Correct	15 ms	10792 KB	Output is correct
16	Correct	13 ms	10792 KB	Output is correct
17	Correct	17 ms	10964 KB	Output is correct
18	Correct	18 ms	11116 KB	Output is correct
19	Correct	63 ms	13896 KB	Output is correct
20	Correct	111 ms	17940 KB	Output is correct
21	Correct	167 ms	21444 KB	Output is correct
22	Correct	250 ms	27048 KB	Output is correct
23	Correct	317 ms	30616 KB	Output is correct
24	Correct	700 ms	41376 KB	Output is correct
25	Correct	590 ms	42016 KB	Output is correct
26	Correct	799 ms	46748 KB	Output is correct
27	Correct	941 ms	51104 KB	Output is correct
28	Correct	903 ms	51428 KB	Output is correct
29	Correct	879 ms	51428 KB	Output is correct
30	Correct	891 ms	51428 KB	Output is correct
31	Correct	877 ms	51872 KB	Output is correct
32	Correct	1034 ms	51872 KB	Output is correct
33	Correct	1099 ms	51872 KB	Output is correct
34	Correct	903 ms	51872 KB	Output is correct
35	Correct	891 ms	51872 KB	Output is correct
36	Correct	17 ms	51872 KB	Output is correct
37	Correct	15 ms	51872 KB	Output is correct
38	Correct	18 ms	51872 KB	Output is correct
39	Correct	55 ms	51872 KB	Output is correct
40	Correct	102 ms	51872 KB	Output is correct
41	Correct	215 ms	51872 KB	Output is correct
42	Correct	320 ms	51872 KB	Output is correct
43	Correct	366 ms	51872 KB	Output is correct
44	Correct	797 ms	55812 KB	Output is correct
45	Correct	693 ms	55812 KB	Output is correct
46	Correct	820 ms	59108 KB	Output is correct
47	Correct	901 ms	72232 KB	Output is correct
48	Correct	1073 ms	77540 KB	Output is correct
49	Correct	953 ms	82368 KB	Output is correct
50	Correct	939 ms	86388 KB	Output is correct
51	Correct	1240 ms	92460 KB	Output is correct
52	Correct	983 ms	97264 KB	Output is correct
53	Correct	982 ms	102216 KB	Output is correct
54	Correct	962 ms	107036 KB	Output is correct
55	Correct	997 ms	112092 KB	Output is correct

답안 #57907

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 30.0 / 30.0

Subtask #3 60.0 / 60.0

Subtask #1
10.0 / 10.0

Subtask #2
30.0 / 30.0

Subtask #3
60.0 / 60.0