oj.uz

Submission #613727

# Submission time Handle Problem Language Result Execution time Memory
613727 2022-07-30T09:52:31 Z andrei_boaca Cake (CEOI14_cake) C++14
100 / 100
 1482 ms 46068 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,q,a,d[300005],where[300005],arb[1200005];
vector<int> nodes[300005],aux;
int nr=0;
set<pii> s;
void update(int nod,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(nod*2,st,mij,poz,val);
    else
        update(nod*2+1,mij+1,dr,poz,val);
    arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
int query(int nod,int st,int dr,int a,int b)
{
    if(st>=a&&dr<=b)
    {
        aux.push_back(nod);
        return arb[nod];
    }
    int rez=0;
    int mij=(st+dr)/2;
    if(a<=mij)
        rez=max(rez,query(nod*2,st,mij,a,b));
    if(b>mij)
        rez=max(rez,query(nod*2+1,mij+1,dr,a,b));
    return rez;
}
int getval(int x)
{
    int rez=0;
    for(int i:nodes[x])
        rez=max(rez,arb[i]);
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>a;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
        s.insert({d[i],i});
        update(1,0,n+1,i,d[i]);
    }
    d[0]=d[n+1]=1e9;
    update(1,0,n+1,0,d[0]);
    update(1,0,n+1,n+1,d[n+1]);
    for(int i=0;i<=n+1;i++)
    {
        aux.clear();
        if(i==a)
            continue;
        if(i<a)
        {
            query(1,0,n+1,i,a-1);
            nodes[i]=aux;
        }
        else
        {
            query(1,0,n+1,a+1,i);
            nodes[i]=aux;
        }
    }
    cin>>q;
    while(q--)
    {
        char c;
        cin>>c;
        if(c=='F')
        {
            int poz;
            cin>>poz;
            int maxim=0;
            if(poz==a)
            {
                cout<<0<<'\n';
                continue;
            }
            if(poz<a)
            {
                maxim=getval(poz);
                int rgt=n+1;
                int st=a+1;
                int dr=n+1;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    int val=getval(mij);
                    if(val>maxim)
                    {
                        rgt=mij;
                        dr=mij-1;
                    }
                    else
                        st=mij+1;
                }
                cout<<rgt-poz-1<<'\n';
            }
            else
            {
                maxim=getval(poz);
                int lft=0;
                int st=0;
                int dr=a-1;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    int val=getval(mij);
                    if(val>maxim)
                    {
                        lft=mij;
                        st=mij+1;
                    }
                    else
                        dr=mij-1;
                }
                cout<<poz-lft-1<<'\n';
            }
        }
        else
        {
            int poz,val;
            cin>>poz>>val;
            int old=d[poz];
            vector<int> mypoz;
            auto it=prev(s.end());
            int cnt=0;
            int myval=0;
            while(cnt+1<val)
            {
                cnt++;
                int p=(*it).second;
                myval=(*it).first;
                mypoz.push_back(p);
                it--;
            }
            if(myval==0)
                myval=(*it).first+1;
            s.erase({d[poz],poz});
            d[poz]=myval;
            s.insert({d[poz],poz});
            update(1,0,n+1,poz,d[poz]);
            for(auto i:mypoz)
            {
                s.erase({d[i],i});
                d[i]++;
                s.insert({d[i],i});
                update(1,0,n+1,i,d[i]);
            }
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:135:17: warning: unused variable 'old' [-Wunused-variable]
  135 |             int old=d[poz];
      |                 ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 9 ms 7520 KB Output is correct
5 Correct 21 ms 8680 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 12032 KB Output is correct
2 Correct 310 ms 11992 KB Output is correct
3 Correct 437 ms 12080 KB Output is correct
4 Correct 193 ms 11892 KB Output is correct
5 Correct 692 ms 13140 KB Output is correct
6 Correct 572 ms 13312 KB Output is correct
7 Correct 424 ms 13320 KB Output is correct
8 Correct 264 ms 13580 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 22348 KB Output is correct
2 Correct 119 ms 22256 KB Output is correct
3 Correct 137 ms 22240 KB Output is correct
4 Correct 5 ms 7252 KB Output is correct
5 Correct 343 ms 43044 KB Output is correct
6 Correct 418 ms 43740 KB Output is correct
7 Correct 220 ms 43596 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8272 KB Output is correct
2 Correct 49 ms 8360 KB Output is correct
3 Correct 175 ms 14808 KB Output is correct
4 Correct 152 ms 14760 KB Output is correct
5 Correct 171 ms 8948 KB Output is correct
6 Correct 225 ms 17436 KB Output is correct
7 Correct 147 ms 10492 KB Output is correct
8 Correct 277 ms 22128 KB Output is correct
9 Correct 1482 ms 45488 KB Output is correct
10 Correct 546 ms 10996 KB Output is correct
11 Correct 736 ms 13912 KB Output is correct
12 Correct 1344 ms 38504 KB Output is correct
13 Correct 1035 ms 46068 KB Output is correct