oj.uz

Submission #257915

# Submission time Handle Problem Language Result Execution time Memory
257915 2020-08-05T04:42:48 Z 최은수(#5047) Employment (JOI16_employment) C++17
0 / 100
 5000 ms 3252 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
const int bs=420;
vector<pair<int*,int> >rbv;
inline void rb()
{
    for(auto&t:rbv)
        *t.fi=t.se;
    rbv.clear();
    return;
}
int n;
int v[200010];
int act[200010];
int acnt;
inline void put(int x,bool t)
{
    if(t)
        rbv.eb(act+x,act[x]);
    act[x]=1;
    if(t)
        rbv.eb(&acnt,acnt);
    acnt++;
    if(act[x-1]==1)
        acnt--;
    if(act[x+1]==1)
        acnt--;
    return;
}
bool chk[200010];
inline void solve(vector<pi>&qv)
{
    for(int i=0;i++<n;)
        chk[i]=0,act[i]=0;
    acnt=0;
    for(pi&t:qv)
        if(t.se>0)
            chk[t.fi]=1;
    vector<int>vv;
    for(int i=0;i++<n;)
        if(!chk[i])
            vv.eb(i);
    sort(all(vv),[&](const int&x,const int&y){return v[x]>v[y];});
    vector<pair<pi,vector<int> > >cqv;
    vector<pi>curv;
    for(int i=0;i++<n;)
        if(chk[i])
            curv.eb(i,v[i]);
    int qcnt=0;
    for(pi&t:qv)
    {
        if(t.se==0)
        {
            vector<int>chv;
            for(pi&ct:curv)
                if(ct.se>=t.fi)
                    chv.eb(ct.fi);
            cqv.eb(pair<pi,vector<int> >(pi(qcnt++,t.fi),chv));
        }
        else
            for(pi&ct:curv)
                if(ct.fi==t.fi)
                    ct=t;
    }
    sort(all(cqv),[](pair<pi,vector<int> >&x,pair<pi,vector<int> >&y){return x.fi.se>y.fi.se;});
    vector<int>ansv(qcnt);
    int j=0;
    for(int&t:vv)
    {
        while(j<(int)cqv.size()&&cqv[j].fi.se>v[t])
        {
            auto&cur=cqv[j];
            j++;
            for(int&ct:cur.se)
                put(ct,1);
            ansv[cur.fi.fi]=acnt;
            rb();
        }
        put(t,0);
    }
    while(j<(int)cqv.size())
    {
        auto&cur=cqv[j];
        j++;
        for(int&ct:cur.se)
            put(ct,1);
        ansv[cur.fi.fi]=acnt;
        rb();
    }
    for(int&t:ansv)
        cout<<t<<'\n';
    for(pi&t:qv)
        if(t.se>0)
            v[t.fi]=t.se;
    qv.clear();
    return;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin>>n>>q;
    for(int i=0;i++<n;)
        cin>>v[i];
    for(int i=0;i<q;i+=bs)
    {
        vector<pi>qv;
        for(int j=0;j<bs&&i+j<q;j++)
        {
            int t,x;
            cin>>t>>x;
            if(t==2)
                cin>>t;
            else
                t--;
            qv.eb(x,t);
        }
        solve(qv);
    }
    cout.flush();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 74 ms 736 KB Output is correct
5 Correct 290 ms 1248 KB Output is correct
6 Correct 655 ms 1496 KB Output is correct
7 Correct 1699 ms 2416 KB Output is correct
8 Correct 2691 ms 2896 KB Output is correct
9 Execution timed out 5091 ms 3252 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -