제출 #157172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157172		easrui	Employment (JOI16_employment)	C++14	100 / 100	355 ms	11912 KiB

employment

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef pair<int,int> pii;
const int MN = 2e5+5;
int A[MN],G[MN],T[4*MN],N,M,S;
vector<int> V;
pii Q[MN];

void upt(int s, int e, int x, int y, int val, int pos)
{
    //if(s==0 && e==S) cout << x << ' ' << y << ' ' << val << '\n';
    if(e<x || y<s) return;
    if(x<=s && e<=y){
        T[pos] += val;
        return;
    }
    int m = (s+e)/2;
    upt(s,m,x,y,val,2*pos);
    upt(m+1,e,x,y,val,2*pos+1);
}

int act(int s, int e, int x, int pos)
{
    if(x<s || e<x) return 0;
    if(s==e) return T[pos];
    int m = (s+e)/2;
    return T[pos]+act(s,m,x,2*pos)+act(m+1,e,x,2*pos+1);
}


bool comb(int x)
{
    return A[x]!=-1&&x<N&&x>1&&A[x]<=A[x-1]&&A[x]<A[x+1];
}

bool isol(int x)
{
    return (x==1||A[x-1]==-1||A[x]>A[x-1])&&(x==N||A[x+1]==-1||A[x]>=A[x+1]);
}

void trans(int x, int val)
{
    if(comb(x)) upt(0,S,0,A[x],1,1);
    if(isol(x)) upt(0,S,0,A[x],-1,1);
    if(x<N){
        if(comb(x+1)) upt(0,S,0,A[x+1],1,1);
        if(!comb(x+1)&&!isol(x+1)&&A[x+1]<=A[x]) upt(0,S,0,A[x+1],1,1);
    }
    if(x>1){
        if(comb(x-1)) upt(0,S,0,A[x-1],1,1);
        if(!comb(x-1)&&!isol(x-1)&&A[x-1]<A[x]) upt(0,S,0,A[x-1],1,1);
    }
    A[x] = -1;
    if(x<N){
        if(isol(x+1)&&A[x+1]<=val) upt(0,S,0,A[x+1],-1,1);
        if(!comb(x+1)&&!isol(x+1)&&A[x+1]<=val) upt(0,S,0,A[x+1],-1,1);
    }
    if(x>1){
        if(isol(x-1)&&A[x-1]<val) upt(0,S,0,A[x-1],-1,1);
        if(!comb(x-1)&&!isol(x-1)&&A[x-1]<val) upt(0,S,0,A[x-1],-1,1);
    }
    A[x] = val;
    if(comb(x)) upt(0,S,0,A[x],-1,1);
    if(isol(x)) upt(0,S,0,A[x],1,1);
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> G[i];
    int T,B,C,D;
    for(int i=0; i<M; i++){
        cin >> T;
        if(T==1){
            cin >> B;
            Q[i] = pii(B,0);
            V.push_back(B);
        }
        if(T==2){
            cin >> C >> D;
            Q[i] = pii(C,D);

        }
    }
    sort(V.begin(),V.end());
    V.erase(unique(V.begin(),V.end()),V.end());
    S = V.size();
    int val;
    for(int i=1; i<=N; i++) A[i] = -1;
    //upt(0,S,0,S-1,1,1);
    for(int i=1; i<=N; i++){
        val = upper_bound(V.begin(),V.end(),G[i])-V.begin()-1;
        //cout << val << '\n';
        trans(i,val);
    }
    //cout << act(0,S,1,1) << '\n';
    //cout << '\n';
    for(int i=0; i<M; i++){
        if(Q[i].vb){
            Q[i].vb = val = upper_bound(V.begin(),V.end(),Q[i].vb)-V.begin()-1;
            //cout << val << '\n';
            trans(Q[i].va,Q[i].vb);
        }
        else{
            Q[i].va = lower_bound(V.begin(),V.end(),Q[i].va)-V.begin();
            cout << act(0,S,Q[i].va,1) << '\n';
        }
    }
}

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