oj.uz

Submission #89295

# Submission time Handle Problem Language Result Execution time Memory
89295 2018-12-11T14:57:05 Z leduykhongngu Employment (JOI16_employment) C++11
10 / 100
 166 ms 44392 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[maxn*8];
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 540 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Correct 6 ms 1592 KB Output is correct
8 Correct 5 ms 1592 KB Output is correct
9 Correct 6 ms 1592 KB Output is correct
10 Correct 7 ms 1900 KB Output is correct
11 Correct 7 ms 1900 KB Output is correct
12 Correct 8 ms 1952 KB Output is correct
13 Correct 8 ms 2048 KB Output is correct
14 Correct 7 ms 2048 KB Output is correct
15 Correct 7 ms 2064 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2064 KB Output is correct
2 Correct 5 ms 2064 KB Output is correct
3 Correct 6 ms 2068 KB Output is correct
4 Correct 26 ms 5192 KB Output is correct
5 Correct 64 ms 11684 KB Output is correct
6 Correct 88 ms 13508 KB Output is correct
7 Correct 166 ms 23000 KB Output is correct
8 Runtime error 118 ms 44392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 540 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 3 ms 1112 KB Output is correct
6 Correct 3 ms 1148 KB Output is correct
7 Correct 6 ms 1592 KB Output is correct
8 Correct 5 ms 1592 KB Output is correct
9 Correct 6 ms 1592 KB Output is correct
10 Correct 7 ms 1900 KB Output is correct
11 Correct 7 ms 1900 KB Output is correct
12 Correct 8 ms 1952 KB Output is correct
13 Correct 8 ms 2048 KB Output is correct
14 Correct 7 ms 2048 KB Output is correct
15 Correct 7 ms 2064 KB Output is correct
16 Correct 4 ms 2064 KB Output is correct
17 Correct 5 ms 2064 KB Output is correct
18 Correct 6 ms 2068 KB Output is correct
19 Correct 26 ms 5192 KB Output is correct
20 Correct 64 ms 11684 KB Output is correct
21 Correct 88 ms 13508 KB Output is correct
22 Correct 166 ms 23000 KB Output is correct
23 Runtime error 118 ms 44392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -