oj.uz

Submission #89297

# Submission time Handle Problem Language Result Execution time Memory
89297 2018-12-11T14:58:06 Z leduykhongngu Employment (JOI16_employment) C++11
100 / 100
 1016 ms 168352 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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