oj.uz

Submission #613642

# Submission time Handle Problem Language Result Execution time Memory
613642 2022-07-30T08:47:04 Z andrei_boaca Cake (CEOI14_cake) C++14
100 / 100
 1778 ms 21488 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,q,a,d[300005],where[300005],arb[1200005];
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;
}
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]);
    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=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]);
            }
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 432 KB Output is correct
5 Correct 31 ms 1108 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 1288 KB Output is correct
2 Correct 329 ms 1400 KB Output is correct
3 Correct 403 ms 1332 KB Output is correct
4 Correct 172 ms 1436 KB Output is correct
5 Correct 677 ms 2264 KB Output is correct
6 Correct 545 ms 2264 KB Output is correct
7 Correct 449 ms 2144 KB Output is correct
8 Correct 231 ms 2352 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 7392 KB Output is correct
2 Correct 220 ms 6988 KB Output is correct
3 Correct 325 ms 6932 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 494 ms 16164 KB Output is correct
6 Correct 550 ms 16288 KB Output is correct
7 Correct 426 ms 15888 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 716 KB Output is correct
2 Correct 69 ms 832 KB Output is correct
3 Correct 213 ms 3832 KB Output is correct
4 Correct 215 ms 3776 KB Output is correct
5 Correct 227 ms 872 KB Output is correct
6 Correct 346 ms 4880 KB Output is correct
7 Correct 248 ms 1624 KB Output is correct
8 Correct 265 ms 6848 KB Output is correct
9 Correct 1778 ms 21488 KB Output is correct
10 Correct 788 ms 1716 KB Output is correct
11 Correct 1002 ms 4084 KB Output is correct
12 Correct 1706 ms 18560 KB Output is correct
13 Correct 1686 ms 21380 KB Output is correct