oj.uz

Submission #258513

# Submission time Handle Problem Language Result Execution time Memory
258513 2020-08-06T05:22:25 Z 최은수(#5046) Vim (BOI13_vim) C++17
0 / 100
 4 ms 1024 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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Incorrect 0 ms 384 KB Output isn't correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Incorrect 0 ms 384 KB Output isn't correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Incorrect 0 ms 384 KB Output isn't correct
14 Incorrect 0 ms 384 KB Output isn't correct
15 Incorrect 0 ms 384 KB Output isn't correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Incorrect 0 ms 384 KB Output isn't correct
18 Incorrect 1 ms 384 KB Output isn't correct
19 Incorrect 0 ms 384 KB Output isn't correct
20 Incorrect 0 ms 384 KB Output isn't correct
21 Incorrect 0 ms 384 KB Output isn't correct
22 Incorrect 0 ms 384 KB Output isn't correct
23 Incorrect 0 ms 384 KB Output isn't correct
24 Incorrect 1 ms 384 KB Output isn't correct
25 Incorrect 0 ms 384 KB Output isn't correct
26 Incorrect 0 ms 384 KB Output isn't correct
27 Incorrect 0 ms 384 KB Output isn't correct
28 Incorrect 1 ms 384 KB Output isn't correct
29 Incorrect 1 ms 384 KB Output isn't correct
30 Incorrect 0 ms 384 KB Output isn't correct
31 Incorrect 0 ms 384 KB Output isn't correct
32 Incorrect 0 ms 384 KB Output isn't correct
33 Incorrect 0 ms 384 KB Output isn't correct
34 Incorrect 1 ms 384 KB Output isn't correct
35 Incorrect 0 ms 384 KB Output isn't correct
36 Incorrect 0 ms 384 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Incorrect 0 ms 384 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 768 KB Output isn't correct
2 Incorrect 2 ms 768 KB Output isn't correct
3 Incorrect 2 ms 768 KB Output isn't correct
4 Incorrect 2 ms 1024 KB Output isn't correct
5 Incorrect 2 ms 1024 KB Output isn't correct
6 Incorrect 2 ms 768 KB Output isn't correct
7 Incorrect 2 ms 768 KB Output isn't correct
8 Incorrect 2 ms 768 KB Output isn't correct
9 Incorrect 3 ms 768 KB Output isn't correct
10 Incorrect 2 ms 768 KB Output isn't correct
11 Incorrect 3 ms 1024 KB Output isn't correct
12 Incorrect 2 ms 1024 KB Output isn't correct
13 Incorrect 2 ms 1024 KB Output isn't correct
14 Incorrect 3 ms 1024 KB Output isn't correct
15 Incorrect 4 ms 1024 KB Output isn't correct
16 Incorrect 2 ms 768 KB Output isn't correct
17 Incorrect 3 ms 768 KB Output isn't correct
18 Incorrect 2 ms 768 KB Output isn't correct
19 Incorrect 2 ms 768 KB Output isn't correct
20 Incorrect 2 ms 768 KB Output isn't correct