oj.uz

Submission #676458

# Submission time Handle Problem Language Result Execution time Memory
676458 2022-12-31T02:48:03 Z vjudge1 Cake (CEOI14_cake) C++17
51.6667 / 100
 2000 ms 17096 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 428 KB Output is correct
5 Correct 54 ms 980 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 3236 KB Time limit exceeded
2 Execution timed out 2075 ms 3148 KB Time limit exceeded
3 Execution timed out 2076 ms 3160 KB Time limit exceeded
4 Execution timed out 2076 ms 2904 KB Time limit exceeded
5 Execution timed out 2074 ms 2964 KB Time limit exceeded
6 Execution timed out 2088 ms 2820 KB Time limit exceeded
7 Execution timed out 2083 ms 3068 KB Time limit exceeded
8 Execution timed out 2073 ms 2952 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7628 KB Output is correct
2 Correct 49 ms 7552 KB Output is correct
3 Correct 52 ms 7644 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 167 ms 17096 KB Output is correct
6 Correct 164 ms 17048 KB Output is correct
7 Correct 104 ms 16816 KB Output is correct

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 956 KB Output is correct
2 Correct 122 ms 1088 KB Output is correct
3 Correct 1353 ms 4460 KB Output is correct
4 Correct 1722 ms 4304 KB Output is correct
5 Correct 246 ms 1864 KB Output is correct
6 Execution timed out 2076 ms 5788 KB Time limit exceeded
7 Correct 868 ms 2884 KB Output is correct
8 Execution timed out 2075 ms 6676 KB Time limit exceeded
9 Execution timed out 2070 ms 16112 KB Time limit exceeded
10 Correct 792 ms 5420 KB Output is correct
11 Execution timed out 2092 ms 4600 KB Time limit exceeded
12 Execution timed out 2088 ms 13192 KB Time limit exceeded
13 Execution timed out 2082 ms 16088 KB Time limit exceeded