oj.uz

Submission #470058

# Submission time Handle Problem Language Result Execution time Memory
470058 2021-09-02T19:30:07 Z MohamedAliSaidane Cake (CEOI14_cake) C++14
10 / 100
 2000 ms 13692 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (int)(1e8)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ld pointdist(ld x, ld y, ld point) { return ((x-point)*(y-point))/abs(x-y); }
//ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
////////////******SOLUTION******\\\\\\\\\\\

const int MAX_N = 1e5 + 4;
int n;
vi A;
int a;
map<int,int> m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> a;
    A.assign(n+2,0);
    A[0] = MOD;
    A[n+1] = MOD+1;
    for(int i = 1; i <=n;  i ++)
        cin >> A[i];
    m[a] = 0;
    int l = a -1;
    int r = a +1;
    int h = 1;
    while(l != 0 || r != n + 1)
    {
        if(A[l] < A[r])
        {
            m[l] = h;
            l --;
        }
        else
        {
            m[r] = h;
            r ++ ;
        }
        h ++;
    }
    int q; cin >> q;
    while(q--)
    {
        char query; cin >> query;
        if(query == 'F')
        {
            int idx; cin >> idx;
            cout << m[idx] << '\n';
        }
        else
        {
            int idx; cin >> idx;
            int e; cin >> e;
            int rang = n - A[idx] + 1;
            A[idx] = n-e+1;
            for(int i = 1; i <= n; i ++)
            {
                if(i == idx)
                    continue;
                int rnk = n - A[i] + 1;
                if(rnk >= e && rnk < rang)
                {
                    A[i]--;
                }
            }
            //for(int i=  1; i <=n; i ++) cout << A[i] << ' ';
            l = a -1;
            r = a +1;
            h = 1;
            while(l != 0 || r != n + 1)
            {
                if(A[l] < A[r])
                {
                    m[l] = h;
                    l --;
                }
                else
                {
                    m[r] = h;
                    r ++ ;
                }
                h ++;
            }
        }
    }
}
/*
Identify problem diagram: Brute force, Greedy, Dynamic Programming, Divide and Conquer
Reformulate the problem into something more theoretical
!!!!! IMPLICIT GRAPH ??????
!!!!! PAY ATTENTION TO THE CONSTRAINTS: DP nD ? BF ? BITMASKING ?
!!!!! SOLVE THE SUBTASKS FIRST: IT'S TOTALLY OK NOT TO SOLVE THE PROBLEM ENTIRELY
Search for multiple approaches: select the seemingly optimal one
Remember that you're the king of CP
Change your approach
Imagine Corner cases before submitting
Don't spend too much time on the problem: move on !
*/

Compilation message

cake.cpp:26:1: warning: multi-line comment [-Wcomment]
   26 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 90 ms 400 KB Output is correct
5 Execution timed out 2066 ms 944 KB Time limit exceeded

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 716 KB Time limit exceeded
2 Execution timed out 2081 ms 716 KB Time limit exceeded
3 Execution timed out 2036 ms 716 KB Time limit exceeded
4 Execution timed out 2079 ms 716 KB Time limit exceeded
5 Execution timed out 2076 ms 1484 KB Time limit exceeded
6 Execution timed out 2085 ms 1484 KB Time limit exceeded
7 Execution timed out 2078 ms 1484 KB Time limit exceeded
8 Execution timed out 2070 ms 1484 KB Time limit exceeded

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 5988 KB Output is correct
2 Correct 920 ms 6124 KB Output is correct
3 Correct 846 ms 5900 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1856 ms 13692 KB Output is correct
6 Execution timed out 2031 ms 13648 KB Time limit exceeded
7 Execution timed out 2075 ms 13468 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 712 KB Time limit exceeded
2 Execution timed out 2076 ms 672 KB Time limit exceeded
3 Execution timed out 2070 ms 2852 KB Time limit exceeded
4 Execution timed out 2068 ms 2852 KB Time limit exceeded
5 Execution timed out 2069 ms 556 KB Time limit exceeded
6 Execution timed out 2078 ms 3724 KB Time limit exceeded
7 Execution timed out 2080 ms 836 KB Time limit exceeded
8 Execution timed out 2077 ms 5316 KB Time limit exceeded
9 Execution timed out 2069 ms 12996 KB Time limit exceeded
10 Execution timed out 2071 ms 580 KB Time limit exceeded
11 Execution timed out 2080 ms 1312 KB Time limit exceeded
12 Execution timed out 2058 ms 10440 KB Time limit exceeded
13 Execution timed out 2086 ms 12940 KB Time limit exceeded