oj.uz

Submission #257923

# Submission time Handle Problem Language Result Execution time Memory
257923 2020-08-05T04:59:11 Z 최은수(#5047) Employment (JOI16_employment) C++17
100 / 100
 3098 ms 6476 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()
{
    reverse(all(rbv));
    for(auto&t:rbv)
        *t.fi=t.se;
    rbv.clear();
    return;
}
int act[200010];
int acnt;
inline void put(int x,bool t)
{
    if(act[x]==1)
        return;
    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,curv;
    for(int&i:vv)
        (chk[i]?curv:vv2).eb(i);
    vector<pair<pi,vector<int> > >cqv;
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 10 ms 640 KB Output is correct
15 Correct 8 ms 640 KB Output is correct

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 21 ms 768 KB Output is correct
5 Correct 71 ms 1412 KB Output is correct
6 Correct 152 ms 1672 KB Output is correct
7 Correct 362 ms 2992 KB Output is correct
8 Correct 548 ms 3472 KB Output is correct
9 Correct 1330 ms 4056 KB Output is correct
10 Correct 1326 ms 5232 KB Output is correct
11 Correct 2076 ms 5772 KB Output is correct
12 Correct 2726 ms 5844 KB Output is correct
13 Correct 2701 ms 5936 KB Output is correct
14 Correct 2492 ms 5908 KB Output is correct
15 Correct 2419 ms 5940 KB Output is correct
16 Correct 2609 ms 6476 KB Output is correct
17 Correct 2585 ms 6024 KB Output is correct
18 Correct 2656 ms 6104 KB Output is correct
19 Correct 2637 ms 6116 KB Output is correct
20 Correct 2583 ms 6188 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 10 ms 640 KB Output is correct
15 Correct 8 ms 640 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 21 ms 768 KB Output is correct
20 Correct 71 ms 1412 KB Output is correct
21 Correct 152 ms 1672 KB Output is correct
22 Correct 362 ms 2992 KB Output is correct
23 Correct 548 ms 3472 KB Output is correct
24 Correct 1330 ms 4056 KB Output is correct
25 Correct 1326 ms 5232 KB Output is correct
26 Correct 2076 ms 5772 KB Output is correct
27 Correct 2726 ms 5844 KB Output is correct
28 Correct 2701 ms 5936 KB Output is correct
29 Correct 2492 ms 5908 KB Output is correct
30 Correct 2419 ms 5940 KB Output is correct
31 Correct 2609 ms 6476 KB Output is correct
32 Correct 2585 ms 6024 KB Output is correct
33 Correct 2656 ms 6104 KB Output is correct
34 Correct 2637 ms 6116 KB Output is correct
35 Correct 2583 ms 6188 KB Output is correct
36 Correct 13 ms 640 KB Output is correct
37 Correct 8 ms 640 KB Output is correct
38 Correct 10 ms 640 KB Output is correct
39 Correct 66 ms 1016 KB Output is correct
40 Correct 162 ms 1148 KB Output is correct
41 Correct 337 ms 1508 KB Output is correct
42 Correct 508 ms 2400 KB Output is correct
43 Correct 802 ms 2728 KB Output is correct
44 Correct 2204 ms 5232 KB Output is correct
45 Correct 1520 ms 4408 KB Output is correct
46 Correct 1835 ms 4608 KB Output is correct
47 Correct 2957 ms 5448 KB Output is correct
48 Correct 3076 ms 5444 KB Output is correct
49 Correct 3003 ms 5752 KB Output is correct
50 Correct 2899 ms 5668 KB Output is correct
51 Correct 3059 ms 5692 KB Output is correct
52 Correct 3098 ms 5736 KB Output is correct
53 Correct 3088 ms 5700 KB Output is correct
54 Correct 3064 ms 5932 KB Output is correct
55 Correct 3072 ms 5764 KB Output is correct