답안 #89297 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89297	2018-12-11T14:58:06 Z	leduykhongngu	Employment (JOI16_employment)	C++11	100 / 100	1016 ms	168352 KB

employment

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for (int i=(a); i>=(b); --i)
#define REP(i,b) for (int i=0; i<(b); ++i)
#define input stdin
#define output stdout
#define assign freopen
#define endl '\n'
#define sz(x) (int) x.size()
#define div /
#define mod %
#define fillchar(x,y,z) memset(x,z,y)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x)*(x))
typedef long long int64;
typedef unsigned long long qword;
using namespace std;
const int maxn=2e5+5;
struct TNode{
    int val,L,R;
};
TNode ST[10000000];
int n,m,cntNode;
int a[maxn];
void Input()
{
    cin >> n >> m;
    FOR(i,1,n)
        cin >> a[i];
}
void update(int id, int l, int r, int u, int val)
{
    if (l>u) return;
    if (r<=u) {
        ST[id].val+=val;
        return;
    }
    int mid=(l+r)>>1;
    if (ST[id].L==0) ST[id].L=++cntNode;
    update(ST[id].L,l,mid,u,val);
    if (mid+1<=u) {
        if (ST[id].R==0) ST[id].R=++cntNode;
        update(ST[id].R,mid+1,r,u,val);
    }
}
int Get(int id, int l, int r, int u)
{
    if (l>u||r<u) return 0;
    if (id==0) return 0;
    int mid=(l+r)>>1;
    return ST[id].val+Get(ST[id].L,l,mid,u)+Get(ST[id].R,mid+1,r,u);
}
void Solve()
{
    cntNode=1;
    FOR(i,1,n)
        update(1,1,1e9,a[i],1);
    FOR(i,2,n)
        update(1,1,1e9,min(a[i],a[i-1]),-1);
    FOR(i,1,m) {
        int typ;
        cin >> typ;
        if (typ==1) {
            int x;
            cin >> x;
            cout << Get(1,1,1e9,x) << endl;
        }
        else {
            int id,x;
            cin >> id >> x;
            if (id>1)
                update(1,1,1e9,min(a[id],a[id-1]),1);
            if (id<n)
                update(1,1,1e9,min(a[id],a[id+1]),1);
            update(1,1,1e9,a[id],-1);
            a[id]=x;
            if (id>1)
                update(1,1,1e9,min(a[id],a[id-1]),-1);
            if (id<n)
                update(1,1,1e9,min(a[id],a[id+1]),-1);
            update(1,1,1e9,a[id],1);
        }
    }
}
int main()
{
    #ifdef meomeomeooooo
        assign("input.txt","r",input);
        //assign(".out","w",output);
    #endif // meomeomeooooo
    iostream::sync_with_stdio(false);
    cin.tie(0);
    Input();
    Solve();
    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	500 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	4 ms	892 KB	Output is correct
5	Correct	3 ms	892 KB	Output is correct
6	Correct	3 ms	892 KB	Output is correct
7	Correct	5 ms	1228 KB	Output is correct
8	Correct	5 ms	1228 KB	Output is correct
9	Correct	5 ms	1228 KB	Output is correct
10	Correct	7 ms	1348 KB	Output is correct
11	Correct	7 ms	1568 KB	Output is correct
12	Correct	7 ms	1568 KB	Output is correct
13	Correct	7 ms	1568 KB	Output is correct
14	Correct	7 ms	1568 KB	Output is correct
15	Correct	7 ms	1568 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1568 KB	Output is correct
2	Correct	5 ms	1568 KB	Output is correct
3	Correct	6 ms	1568 KB	Output is correct
4	Correct	27 ms	4072 KB	Output is correct
5	Correct	63 ms	9788 KB	Output is correct
6	Correct	88 ms	10612 KB	Output is correct
7	Correct	157 ms	18676 KB	Output is correct
8	Correct	192 ms	22060 KB	Output is correct
9	Correct	337 ms	31304 KB	Output is correct
10	Correct	383 ms	47520 KB	Output is correct
11	Correct	399 ms	47520 KB	Output is correct
12	Correct	456 ms	56688 KB	Output is correct
13	Correct	474 ms	61964 KB	Output is correct
14	Correct	459 ms	64968 KB	Output is correct
15	Correct	458 ms	68996 KB	Output is correct
16	Correct	478 ms	74828 KB	Output is correct
17	Correct	465 ms	79048 KB	Output is correct
18	Correct	511 ms	83352 KB	Output is correct
19	Correct	483 ms	87680 KB	Output is correct
20	Correct	505 ms	91384 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	500 KB	Output is correct
3	Correct	2 ms	508 KB	Output is correct
4	Correct	4 ms	892 KB	Output is correct
5	Correct	3 ms	892 KB	Output is correct
6	Correct	3 ms	892 KB	Output is correct
7	Correct	5 ms	1228 KB	Output is correct
8	Correct	5 ms	1228 KB	Output is correct
9	Correct	5 ms	1228 KB	Output is correct
10	Correct	7 ms	1348 KB	Output is correct
11	Correct	7 ms	1568 KB	Output is correct
12	Correct	7 ms	1568 KB	Output is correct
13	Correct	7 ms	1568 KB	Output is correct
14	Correct	7 ms	1568 KB	Output is correct
15	Correct	7 ms	1568 KB	Output is correct
16	Correct	4 ms	1568 KB	Output is correct
17	Correct	5 ms	1568 KB	Output is correct
18	Correct	6 ms	1568 KB	Output is correct
19	Correct	27 ms	4072 KB	Output is correct
20	Correct	63 ms	9788 KB	Output is correct
21	Correct	88 ms	10612 KB	Output is correct
22	Correct	157 ms	18676 KB	Output is correct
23	Correct	192 ms	22060 KB	Output is correct
24	Correct	337 ms	31304 KB	Output is correct
25	Correct	383 ms	47520 KB	Output is correct
26	Correct	399 ms	47520 KB	Output is correct
27	Correct	456 ms	56688 KB	Output is correct
28	Correct	474 ms	61964 KB	Output is correct
29	Correct	459 ms	64968 KB	Output is correct
30	Correct	458 ms	68996 KB	Output is correct
31	Correct	478 ms	74828 KB	Output is correct
32	Correct	465 ms	79048 KB	Output is correct
33	Correct	511 ms	83352 KB	Output is correct
34	Correct	483 ms	87680 KB	Output is correct
35	Correct	505 ms	91384 KB	Output is correct
36	Correct	6 ms	91384 KB	Output is correct
37	Correct	4 ms	91384 KB	Output is correct
38	Correct	9 ms	91384 KB	Output is correct
39	Correct	53 ms	91384 KB	Output is correct
40	Correct	105 ms	91384 KB	Output is correct
41	Correct	180 ms	91384 KB	Output is correct
42	Correct	268 ms	91384 KB	Output is correct
43	Correct	406 ms	91384 KB	Output is correct
44	Correct	785 ms	112060 KB	Output is correct
45	Correct	594 ms	112060 KB	Output is correct
46	Correct	653 ms	112844 KB	Output is correct
47	Correct	952 ms	129424 KB	Output is correct
48	Correct	893 ms	134132 KB	Output is correct
49	Correct	746 ms	139324 KB	Output is correct
50	Correct	759 ms	142548 KB	Output is correct
51	Correct	792 ms	149680 KB	Output is correct
52	Correct	766 ms	154380 KB	Output is correct
53	Correct	830 ms	159492 KB	Output is correct
54	Correct	1016 ms	164312 KB	Output is correct
55	Correct	984 ms	168352 KB	Output is correct

답안 #89297

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