oj.uz

Submission #160739

# Submission time Handle Problem Language Result Execution time Memory
160739 2019-10-29T16:31:05 Z shashwatchandra Cake (CEOI14_cake) C++17
15 / 100
 2000 ms 5616 KB 
/*input
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5

3
1
0
1
2
3
1
0
1
2
3
1
0
1
2
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 2e5+1;
int n,a;
int pos[N];


void solve(){
  	cin >> n >> a;
  	RE(i,n){
  		cin >> pos[i];
  	}
  	int q;cin >> q;
  	while(q--){
  		char o;cin >> o;
  		if(o == 'E'){
  			int ind,newpos;
  			cin >> ind >> newpos;
  			newpos = n-newpos+1;
  			RE(i,n){
  				if(i == ind)continue;
  				if(pos[i] >= newpos and pos[i] < pos[ind])pos[i]++;
  				else if(pos[i] > pos[ind] and newpos >= pos[i])pos[i]--;
  			}
  			pos[ind] = newpos;
  			RE(i,n){
  		//		cout << pos[i] << " ";
  			}
  		//	cout << endl;
  		}
  		else{
  			int b;cin >> b;
  			if(b == a){
  				cout << 0 << endl;
  				continue;
  			}
  			else if(b < a){
  				int times = n-b;
  				int maxx = 0;
  				for(int i = b;i < a;i++)maxx = max(maxx,pos[i]);
  				//cout << "PRINTING FOR " << b << endl;
  				///cout << maxx << endl;
  				for(int j = a+1;j <= n;j++){
  					if(pos[j] > maxx){
  					//	cout << j << " " << pos[j] << endl;
  						times = (j-1)-b;
  						break;
  					}
  				}
  				cout << times << endl;
  			}
  			else{
  				int times = b-1;
  				int maxx = 0;
  				for(int i = a+1;i <= b;i++)maxx = max(maxx,pos[i]);
  					//cout << "WOWO " << maxx << endl;
  				for(int j = a-1;j > 0;j--){
  					if(pos[j] > maxx){
  						times = b-(j+1);
  						break;
  					}
  				}
  				cout << times << endl;
  			}
  		}
  	}
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 21 ms 376 KB Output is correct
5 Correct 249 ms 632 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 1788 KB Time limit exceeded
2 Execution timed out 2061 ms 2396 KB Time limit exceeded
3 Execution timed out 2050 ms 1912 KB Time limit exceeded
4 Execution timed out 2033 ms 2524 KB Time limit exceeded
5 Execution timed out 2060 ms 1248 KB Time limit exceeded
6 Execution timed out 2062 ms 1656 KB Time limit exceeded
7 Execution timed out 2059 ms 1404 KB Time limit exceeded
8 Execution timed out 2063 ms 1716 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 2756 KB Time limit exceeded
2 Execution timed out 2062 ms 3104 KB Time limit exceeded
3 Execution timed out 2045 ms 3072 KB Time limit exceeded
4 Correct 2 ms 376 KB Output is correct
5 Runtime error 52 ms 5112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Execution timed out 2060 ms 4268 KB Time limit exceeded
7 Execution timed out 2067 ms 3852 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 888 KB Output is correct
2 Correct 659 ms 1120 KB Output is correct
3 Execution timed out 2083 ms 1656 KB Time limit exceeded
4 Execution timed out 2065 ms 1804 KB Time limit exceeded
5 Correct 898 ms 1928 KB Output is correct
6 Execution timed out 2062 ms 1656 KB Time limit exceeded
7 Execution timed out 2061 ms 1808 KB Time limit exceeded
8 Execution timed out 2053 ms 2044 KB Time limit exceeded
9 Runtime error 31 ms 5112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Execution timed out 2054 ms 3908 KB Time limit exceeded
11 Execution timed out 2067 ms 1620 KB Time limit exceeded
12 Execution timed out 2045 ms 3600 KB Time limit exceeded
13 Runtime error 729 ms 5616 KB Execution killed with signal 11 (could be triggered by violating memory limits)