oj.uz

Submission #613654

# Submission time Handle Problem Language Result Execution time Memory
613654 2022-07-30T08:54:18 Z andrei_boaca Cake (CEOI14_cake) C++14
100 / 100
 1683 ms 21972 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,q,a,d[300005],where[300005],arb[1200005];
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)
        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;
}
void compute()
{
    where[a]=1;
    int st=a-1;
    int dr=a+1;
    int cnt=1;
    while(st>0||dr<=n)
    {
        cnt++;
        if(d[st]<d[dr])
        {
            where[st]=cnt;
            st--;
        }
        else
        {
            where[dr]=cnt;
            dr++;
        }
    }
}
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]);
    compute();
    cin>>q;
    while(q--)
    {
        char c;
        cin>>c;
        if(c=='F')
        {
            int poz;
            cin>>poz;
            if(nr<1000)
            {
                cout<<where[poz]-1<<'\n';
                continue;
            }
            int maxim=0;
            if(poz==a)
            {
                cout<<0<<'\n';
                continue;
            }
            if(poz<a)
            {
                maxim=query(1,0,n+1,poz,a-1);
                int rgt=n+1;
                int st=a+1;
                int dr=n+1;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    int val=query(1,0,n+1,a+1,mij);
                    if(val>maxim)
                    {
                        rgt=mij;
                        dr=mij-1;
                    }
                    else
                        st=mij+1;
                }
                cout<<rgt-poz-1<<'\n';
            }
            else
            {
                maxim=query(1,0,n+1,a+1,poz);
                int lft=0;
                int st=0;
                int dr=a-1;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    int val=query(1,0,n+1,mij,a-1);
                    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]);
            }
            if(nr<100)
            {
                nr++;
                compute();
            }
            else
                nr=10000;
        }
    }
    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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 23 ms 1160 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 3232 KB Output is correct
2 Correct 288 ms 3236 KB Output is correct
3 Correct 353 ms 3292 KB Output is correct
4 Correct 166 ms 3220 KB Output is correct
5 Correct 633 ms 4124 KB Output is correct
6 Correct 509 ms 4248 KB Output is correct
7 Correct 380 ms 4172 KB Output is correct
8 Correct 223 ms 4156 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 8572 KB Output is correct
2 Correct 60 ms 8272 KB Output is correct
3 Correct 62 ms 8172 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 197 ms 18256 KB Output is correct
6 Correct 209 ms 18248 KB Output is correct
7 Correct 132 ms 17796 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 928 KB Output is correct
2 Correct 68 ms 1076 KB Output is correct
3 Correct 176 ms 4728 KB Output is correct
4 Correct 189 ms 4800 KB Output is correct
5 Correct 206 ms 1732 KB Output is correct
6 Correct 334 ms 6608 KB Output is correct
7 Correct 233 ms 2892 KB Output is correct
8 Correct 249 ms 8780 KB Output is correct
9 Correct 1683 ms 21916 KB Output is correct
10 Correct 698 ms 2464 KB Output is correct
11 Correct 951 ms 5916 KB Output is correct
12 Correct 1549 ms 19456 KB Output is correct
13 Correct 1553 ms 21972 KB Output is correct