Submission #114348

#	Time	Username	Problem	Language	Result	Execution time	Memory
114348		onjo0127	Employment (JOI16_employment)	C++11	100 / 100	242 ms	13188 KiB

employment

#include <bits/stdc++.h>
using namespace std;

struct query {
    int ty, a, b;
} B[200009];

vector<int> S;
int A[200009], C[200009], F[400009];

int f(int x) {
    return (int)S.size() - (lower_bound(S.begin(), S.end(), x) - S.begin());
}

void upd(int x, int y) { for(int i=x; i<=(int)S.size(); i+=(i&-i)) F[i] += y; }
int get(int x) {int s = 0; for(int i=x; i>=1; i-=(i&-i)) s += F[i]; return s; }

void update(int id, int nw) {
    upd(A[id], -C[id]);
    A[id] = nw;
    if(A[id-1] <= A[id] && A[id+1] < A[id]) C[id] = -1;
    else if(A[id-1] > A[id] && A[id+1] >= A[id]) C[id] = +1;
    else C[id] = 0;
    upd(A[id], C[id]);
}

int main() {
    int N, M; scanf("%d%d",&N,&M);
    for(int i=1; i<=N; i++) {
        scanf("%d",&A[i]);
        S.push_back(A[i]);
    } A[0] = A[N+1] = 1e9;
    for(int i=0; i<M; i++) {
        int t, a, b = -1; scanf("%d",&t);
        if(t == 1) {
            scanf("%d",&a);
            S.push_back(a);
        }
        else {
            scanf("%d%d",&a,&b);
            S.push_back(b);
        }
        B[i] = {t, a, b};
    }
    sort(S.begin(), S.end()); S.resize(unique(S.begin(), S.end()) - S.begin());
    for(int i=1; i<=N; i++) A[i] = f(A[i]);
    for(int i=0; i<M; i++) {
        if(B[i].ty == 1) B[i].a = f(B[i].a);
        else B[i].b = f(B[i].b);
    }
    for(int i=1; i<=N; i++) {
        if(A[i-1] <= A[i] && A[i+1] < A[i]) C[i] = -1;
        else if(A[i-1] > A[i] && A[i+1] >= A[i]) C[i] = +1;
        else C[i] = 0;
        upd(A[i], C[i]);
    }
    for(int i=0; i<M; i++) {
        if(B[i].ty == 1) printf("%d\n", get(B[i].a));
        else {
            int id = B[i].a, nw = B[i].b;
            update(id, nw);
            if(id != 1) update(id-1, A[id-1]);
            if(id != N) update(id+1, A[id+1]);
        }
    }
    return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:28:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d%d",&N,&M);
               ~~~~~^~~~~~~~~~~~~~
employment.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~
employment.cpp:34:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, a, b = -1; scanf("%d",&t);
                           ~~~~~^~~~~~~~~
employment.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~
employment.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60