oj.uz

Submission #613626

# Submission time Handle Problem Language Result Execution time Memory
613626 2022-07-30T08:23:35 Z andrei_boaca Cake (CEOI14_cake) C++14
51.6667 / 100
 2000 ms 15196 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,q,a,d[300005],where[300005];
set<pii> s;
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});
    }
    d[0]=d[n+1]=1e9;
    compute();
    cin>>q;
    while(q--)
    {
        char c;
        cin>>c;
        if(c=='F')
        {
            int poz;
            cin>>poz;
            cout<<where[poz]-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});
            for(auto i:mypoz)
            {
                s.erase({d[i],i});
                d[i]++;
                s.insert({d[i],i});
            }
            compute();
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:55:17: warning: unused variable 'old' [-Wunused-variable]
   55 |             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 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 340 KB Output is correct
5 Correct 59 ms 896 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 724 KB Time limit exceeded
2 Execution timed out 2082 ms 852 KB Time limit exceeded
3 Execution timed out 2050 ms 852 KB Time limit exceeded
4 Execution timed out 2081 ms 852 KB Time limit exceeded
5 Execution timed out 2074 ms 1636 KB Time limit exceeded
6 Execution timed out 2075 ms 1620 KB Time limit exceeded
7 Execution timed out 2071 ms 1620 KB Time limit exceeded
8 Execution timed out 2068 ms 1620 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 6400 KB Output is correct
2 Correct 51 ms 6236 KB Output is correct
3 Correct 59 ms 6112 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 201 ms 15000 KB Output is correct
6 Correct 186 ms 15196 KB Output is correct
7 Correct 103 ms 14536 KB Output is correct

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 524 KB Output is correct
2 Correct 121 ms 596 KB Output is correct
3 Correct 1524 ms 3392 KB Output is correct
4 Correct 1748 ms 3464 KB Output is correct
5 Correct 244 ms 756 KB Output is correct
6 Execution timed out 2086 ms 4236 KB Time limit exceeded
7 Correct 907 ms 1416 KB Output is correct
8 Execution timed out 2050 ms 5708 KB Time limit exceeded
9 Execution timed out 2086 ms 14084 KB Time limit exceeded
10 Correct 823 ms 1508 KB Output is correct
11 Execution timed out 2077 ms 2232 KB Time limit exceeded
12 Execution timed out 2070 ms 11552 KB Time limit exceeded
13 Execution timed out 2078 ms 14168 KB Time limit exceeded