oj.uz

Submission #257920

# Submission time Handle Problem Language Result Execution time Memory
257920 2020-08-05T04:51:49 Z 최은수(#5047) Employment (JOI16_employment) C++17
30 / 100
 2127 ms 6376 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=632;
vector<pair<int*,int> >rbv;
inline void rb()
{
    for(auto&t:rbv)
        *t.fi=t.se;
    rbv.clear();
    return;
}
int act[200010];
int acnt;
inline void put(int x,bool t)
{
    if(t)
        rbv.eb(act+x,0);
    act[x]=1;
    if(t)
        rbv.eb(&acnt,acnt);
    acnt++;
    if(act[x-1]==1)
        acnt--;
    if(act[x+1]==1)
        acnt--;
    return;
}
int n;
int v[200010];
bool chk[200010];
vector<int>vv;
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>vv2;
    for(int&i:vv)
        if(!chk[i])
            vv2.eb(i);
    vector<pair<pi,vector<int> > >cqv;
    vector<int>curv;
    for(int i=0;i++<n;)
        if(chk[i])
            curv.eb(i);
    int qcnt=0;
    for(pi&t:qv)
    {
        if(t.se==0)
        {
            vector<int>chv;
            for(int&ct:curv)
                if(v[ct]>=t.fi)
                    chv.eb(ct);
            cqv.eb(pair<pi,vector<int> >(pi(qcnt++,t.fi),chv));
        }
        else
            v[t.fi]=t.se;
    }
    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:vv2)
    {
        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';
    sort(all(curv),[&](const int&x,const int&y){return v[x]>v[y];});
    vv.clear();
    {
        int i=0,j=0;
        while(i<(int)vv2.size()&&j<(int)curv.size())
        {
            if(v[vv2[i]]>v[curv[j]])
                vv.eb(vv2[i++]);
            else
                vv.eb(curv[j++]);
        }
        while(i<(int)vv2.size()||j<(int)curv.size())
        {
            if(i<(int)vv2.size())
                vv.eb(vv2[i++]);
            else
                vv.eb(curv[j++]);
        }
    }
    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],vv.eb(i);
    sort(all(vv),[&](const int&x,const int&y){return v[x]>v[y];});
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 20 ms 768 KB Output is correct
5 Correct 63 ms 1476 KB Output is correct
6 Correct 129 ms 1704 KB Output is correct
7 Correct 306 ms 2728 KB Output is correct
8 Correct 458 ms 3008 KB Output is correct
9 Correct 1095 ms 4128 KB Output is correct
10 Correct 1018 ms 5384 KB Output is correct
11 Correct 1670 ms 5600 KB Output is correct
12 Correct 2021 ms 6072 KB Output is correct
13 Correct 2032 ms 6228 KB Output is correct
14 Correct 1936 ms 6068 KB Output is correct
15 Correct 1991 ms 6124 KB Output is correct
16 Correct 2123 ms 6328 KB Output is correct
17 Correct 2039 ms 5948 KB Output is correct
18 Correct 2127 ms 6296 KB Output is correct
19 Correct 2117 ms 6376 KB Output is correct
20 Correct 2108 ms 6360 KB Output is correct

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 -