Submission #89297

#	Time	Username	Problem	Language	Result	Execution time	Memory
89297		leduykhongngu	Employment (JOI16_employment)	C++11	100 / 100	1016 ms	168352 KiB

employment

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60