Submission #466365

#	Time	Username	Problem	Language	Result	Execution time	Memory
466365		Namnamseo	Employment (JOI16_employment)	C++17	100 / 100	487 ms	12600 KiB

employment

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define ind(x,y) lower_bound(all(x), y) - x.begin() + 1

const int M = 524288;

int tree[M<<1];
void upd(int l,int r,int v){
    l+=M; r+=M;
    while(l<=r){
        if(l%2==1) tree[l++]+=v;
        if(r%2==0) tree[r--]+=v;
        l>>=1; r>>=1;
    }
}

int get(int x){
    x+=M; int ret=0;
    while(x) ret+=tree[x], x>>=1;
    return ret;
}

vector<int> yp;

int qtype[200010];
int qx[200010];
int qy[200010];
int n, q;

int val[200010];

void treat(int pos,int dt){
    int a=val[pos], b=val[pos+1];
    a=ind(yp, a); b=ind(yp, b);
    if(a>b) upd(b+1, a, dt);
}

int main()
{
    yp.pb(0);
    scanf("%d%d",&n, &q);
    for(int i=1; i<=n; ++i){
        scanf("%d", val+i);
        yp.pb(val[i]);
    }

    for(int i=1; i<=q; ++i){
        scanf("%d", qtype+i);
        if(qtype[i] == 1){
            scanf("%d", qx+i);
        } else {
            scanf("%d", qx+i);
            scanf("%d", qy+i);
            yp.pb(qy[i]);
        }
    }

    sort(all(yp));
    yp.erase(unique(all(yp)), yp.end());

    for(int i=1; i<=n; ++i){
        treat(i, 1);
    }

    for(int i=1; i<=q; ++i){
        if(qtype[i] == 1){
            int a=ind(yp, qx[i]);
            printf("%d\n", get(a));
        } else {
            int a=qx[i], b=qy[i];
            if(1<a) treat(a-1, -1);
            treat(a, -1);
            val[a]=b;
            if(1<a) treat(a-1, 1);
            treat(a, 1);
        }
    }
    return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d",&n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~
employment.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d", val+i);
      |         ~~~~~^~~~~~~~~~~~~
employment.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d", qtype+i);
      |         ~~~~~^~~~~~~~~~~~~~~
employment.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |             scanf("%d", qx+i);
      |             ~~~~~^~~~~~~~~~~~
employment.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |             scanf("%d", qx+i);
      |             ~~~~~^~~~~~~~~~~~
employment.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |             scanf("%d", qy+i);
      |             ~~~~~^~~~~~~~~~~~

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