Submission #576117

#	Time	Username	Problem	Language	Result	Execution time	Memory
576117		urd05	Employment (JOI16_employment)	C++17	100 / 100	305 ms	14888 KiB

employment

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

typedef pair<int,int> P;
typedef pair<P,int> Pi;
int val[200001];
P a[200002];
int n,m;
vector<Pi> query;
vector<int> pr;
const int sz=524288;
int seg[sz*2];

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}

void update(int i,int x) {
    i+=sz;
    seg[i]+=x;
    while (i>1) {
        i/=2;
        seg[i]=seg[i*2]+seg[i*2+1];
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i].first);
        a[i].second=i;
        pr.push_back(a[i].first);
    }
    for(int i=0;i<m;i++) {
        int t;
        scanf("%d",&t);
        if (t==1) {
            int b;
            scanf("%d",&b);
            query.push_back(Pi(P(t,b),-1));
        }
        else {
            int c,d;
            scanf("%d %d",&c,&d);
            pr.push_back(d);
            query.push_back(Pi(P(t,c),d));
        }
    }
    sort(pr.begin(),pr.end());
    pr.erase(unique(pr.begin(),pr.end()),pr.end());
    for(int i=1;i<=n;i++) {
        val[i]=1;
        if (a[i-1]>a[i]) {
            val[i]--;
        }
        if (a[i+1]>a[i]) {
            val[i]--;
        }
        int ind=lower_bound(pr.begin(),pr.end(),a[i].first)-pr.begin();
        update(ind,val[i]);
    }
    for(int i=0;i<m;i++) {
        if (query[i].first.first==1) {
            int b=query[i].first.second;
            int ind=lower_bound(pr.begin(),pr.end(),b)-pr.begin();
            printf("%d\n",sum(ind,sz-1));
        }
        else {
            int c=query[i].first.second;
            int d=query[i].second;
            int ind=lower_bound(pr.begin(),pr.end(),a[c].first)-pr.begin();
            update(ind,-val[c]);
            int temp[3];
            memset(temp,0,sizeof(temp));
            if (a[c-1]<a[c]) {
                temp[0]++;
            }
            if (a[c]>a[c+1]) {
                temp[2]++;
            }
            a[c]=P(d,c);
            temp[1]=1;
            if (a[c-1]<a[c]) {
                temp[0]--;
            }
            else {
                temp[1]--;
            }
            if (a[c]<a[c+1]) {
                temp[1]--;
            }
            else {
                temp[2]--;
            }
            if (c!=1) {
                int ind0=lower_bound(pr.begin(),pr.end(),a[c-1].first)-pr.begin();
                update(ind0,temp[0]);
                val[c-1]+=temp[0];
            }
            int ind1=lower_bound(pr.begin(),pr.end(),a[c].first)-pr.begin();
            update(ind1,temp[1]);
            val[c]=temp[1];
            if (c!=n) {
                int ind2=lower_bound(pr.begin(),pr.end(),a[c+1].first)-pr.begin();
                update(ind2,temp[2]);
                val[c+1]+=temp[2];
            }
        }
    }
    return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
employment.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d",&a[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
employment.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
employment.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |             scanf("%d",&b);
      |             ~~~~~^~~~~~~~~
employment.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf("%d %d",&c,&d);
      |             ~~~~~^~~~~~~~~~~~~~~

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