답안 #55385 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55385	2018-07-07T06:22:32 Z	노영훈(#1544)	Employment (JOI16_employment)	C++11	100 / 100	376 ms	9904 KB

employment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9, XMX=400010;

int n, q;
int A[MX];

struct query{
    int type, x, y;
    void scan(){
        cin>>type>>x;
        if(type==2) cin>>y;
    }
} Q[MX];

vector<int> X;
int find(int x){
    return lower_bound(X.begin(), X.end(), x)-X.begin()+1;
}
int lim;

struct BIT {
    int tree[XMX], n;
    void init(int sz){
        n=sz;
        for(int i=1; i<=n; i++) tree[i]=0;
    }
    void upt(int pos, int val){
        if(val==0) return;
        for(; 0<pos && pos<=n; pos+=pos&(-pos))
            tree[pos]+=val;
    }
    int sum(int x){
        int res=0;
        for(; 0<x; x-=x&(-x)) res+=tree[x];
        return res;
    }
    int sum(int l, int r){
        return sum(r)-sum(l-1);
    }
} Vtree, Etree;


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        cin>>A[i];
        X.push_back(A[i]);
    }
    for(int i=1; i<=q; i++){
        Q[i].scan();
        if(Q[i].type==2)
            X.push_back(Q[i].y);
        else
            X.push_back(Q[i].x);
    }
    sort(X.begin(), X.end());
    lim=unique(X.begin(), X.end())-X.begin();
    X.resize(lim);
    for(int i=1; i<=n; i++) A[i]=find(A[i]);
    for(int i=1; i<=q; i++)
        if(Q[i].type==2) Q[i].y=find(Q[i].y);
        else Q[i].x=find(Q[i].x);

    Vtree.init(lim);
    Etree.init(lim);

    for(int i=1; i<=n; i++) Vtree.upt(A[i], 1);
    for(int i=1; i<=n; i++){
        if(1<i) Etree.upt(A[i], A[i-1]>A[i]);
        if(i<n) Etree.upt(A[i], A[i+1]>=A[i]);
    }

    for(int idx=1; idx<=q; idx++){
        if(Q[idx].type==1){
            cout<<Vtree.sum(Q[idx].x, lim) - Etree.sum(Q[idx].x, lim)<<'\n';
        }
        else{
            int i=Q[idx].x, b=Q[idx].y, a=A[i]; // a -> b
            A[i]=b;

            Vtree.upt(a,-1); Vtree.upt(b,1);

            if(1<i) Etree.upt(a, -(A[i-1]>a)), Etree.upt(A[i-1], -(a>=A[i-1]));
            if(i<n) Etree.upt(a, -(A[i+1]>=a)), Etree.upt(A[i+1], -(a>A[i+1]));

            if(1<i) Etree.upt(b, (A[i-1]>b)), Etree.upt(A[i-1], (b>=A[i-1]));
            if(i<n) Etree.upt(b, (A[i+1]>=b)), Etree.upt(A[i+1], (b>A[i+1]));
        }
    }

    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	396 KB	Output is correct
4	Correct	3 ms	412 KB	Output is correct
5	Correct	3 ms	412 KB	Output is correct
6	Correct	3 ms	412 KB	Output is correct
7	Correct	4 ms	724 KB	Output is correct
8	Correct	5 ms	724 KB	Output is correct
9	Correct	4 ms	724 KB	Output is correct
10	Correct	4 ms	724 KB	Output is correct
11	Correct	5 ms	744 KB	Output is correct
12	Correct	4 ms	744 KB	Output is correct
13	Correct	4 ms	748 KB	Output is correct
14	Correct	4 ms	748 KB	Output is correct
15	Correct	4 ms	748 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	4 ms	780 KB	Output is correct
4	Correct	22 ms	1476 KB	Output is correct
5	Correct	36 ms	2092 KB	Output is correct
6	Correct	65 ms	3116 KB	Output is correct
7	Correct	79 ms	4184 KB	Output is correct
8	Correct	105 ms	5080 KB	Output is correct
9	Correct	175 ms	8108 KB	Output is correct
10	Correct	191 ms	8108 KB	Output is correct
11	Correct	246 ms	8876 KB	Output is correct
12	Correct	294 ms	9644 KB	Output is correct
13	Correct	255 ms	9816 KB	Output is correct
14	Correct	230 ms	9816 KB	Output is correct
15	Correct	252 ms	9816 KB	Output is correct
16	Correct	282 ms	9904 KB	Output is correct
17	Correct	276 ms	9904 KB	Output is correct
18	Correct	278 ms	9904 KB	Output is correct
19	Correct	273 ms	9904 KB	Output is correct
20	Correct	241 ms	9904 KB	Output is correct

Subtask #3
60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	396 KB	Output is correct
4	Correct	3 ms	412 KB	Output is correct
5	Correct	3 ms	412 KB	Output is correct
6	Correct	3 ms	412 KB	Output is correct
7	Correct	4 ms	724 KB	Output is correct
8	Correct	5 ms	724 KB	Output is correct
9	Correct	4 ms	724 KB	Output is correct
10	Correct	4 ms	724 KB	Output is correct
11	Correct	5 ms	744 KB	Output is correct
12	Correct	4 ms	744 KB	Output is correct
13	Correct	4 ms	748 KB	Output is correct
14	Correct	4 ms	748 KB	Output is correct
15	Correct	4 ms	748 KB	Output is correct
16	Correct	5 ms	768 KB	Output is correct
17	Correct	5 ms	768 KB	Output is correct
18	Correct	4 ms	780 KB	Output is correct
19	Correct	22 ms	1476 KB	Output is correct
20	Correct	36 ms	2092 KB	Output is correct
21	Correct	65 ms	3116 KB	Output is correct
22	Correct	79 ms	4184 KB	Output is correct
23	Correct	105 ms	5080 KB	Output is correct
24	Correct	175 ms	8108 KB	Output is correct
25	Correct	191 ms	8108 KB	Output is correct
26	Correct	246 ms	8876 KB	Output is correct
27	Correct	294 ms	9644 KB	Output is correct
28	Correct	255 ms	9816 KB	Output is correct
29	Correct	230 ms	9816 KB	Output is correct
30	Correct	252 ms	9816 KB	Output is correct
31	Correct	282 ms	9904 KB	Output is correct
32	Correct	276 ms	9904 KB	Output is correct
33	Correct	278 ms	9904 KB	Output is correct
34	Correct	273 ms	9904 KB	Output is correct
35	Correct	241 ms	9904 KB	Output is correct
36	Correct	3 ms	9904 KB	Output is correct
37	Correct	4 ms	9904 KB	Output is correct
38	Correct	4 ms	9904 KB	Output is correct
39	Correct	18 ms	9904 KB	Output is correct
40	Correct	37 ms	9904 KB	Output is correct
41	Correct	64 ms	9904 KB	Output is correct
42	Correct	103 ms	9904 KB	Output is correct
43	Correct	160 ms	9904 KB	Output is correct
44	Correct	303 ms	9904 KB	Output is correct
45	Correct	233 ms	9904 KB	Output is correct
46	Correct	236 ms	9904 KB	Output is correct
47	Correct	319 ms	9904 KB	Output is correct
48	Correct	328 ms	9904 KB	Output is correct
49	Correct	303 ms	9904 KB	Output is correct
50	Correct	376 ms	9904 KB	Output is correct
51	Correct	319 ms	9904 KB	Output is correct
52	Correct	329 ms	9904 KB	Output is correct
53	Correct	338 ms	9904 KB	Output is correct
54	Correct	318 ms	9904 KB	Output is correct
55	Correct	335 ms	9904 KB	Output is correct

답안 #55385

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