oj.uz

Submission #386196

# Submission time Handle Problem Language Result Execution time Memory
386196 2021-04-06T04:12:46 Z Kalashnikov Simple game (IZhO17_game) C++17
22 / 100
 1000 ms 6904 KB 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int h[N] , u[N] , ans[N] , pos[N] , val[N] , type[N] , prank[N];
int K = 400;

struct node{
	int l ,r , pix;
}t[4*N];
int n , q;

void upd(int pos , int val = 1 , int u = 1, int ul = 1, int ur = n) {
	if(ul == ur) {
		t[u].l = val;
		t[u].r = val;
		return;
	}
	
	int um = ul+ur >> 1;
	if(pos <= um) {
		upd(pos , val , u<<1 , ul , um);
	}
	else {
		upd(pos , val , u<<1|1 , um+1 , ur);
	}
	t[u].l = t[u<<1].l;
	t[u].r = t[u<<1|1].r;
	t[u].pix = t[u<<1].pix + t[u<<1|1].pix + (t[u<<1].r != t[u<<1|1].l);
}

void solve() {	
	cin >> n >> q;
	for(int i = 1; i <= n; i ++)  {
		cin >> h[i];
	}
	int last = 0;
	for(int i = 0; i <= q; i ++) {
		if((i%K == 0 && i != 0) || i == q) {
			vector<pair<int,int>> cons;
			for(int i = 1; i <= n; i ++) {
				if(u[i] == 0) {
					cons.push_back({h[i] , i});
				}
				
				u[i] = 0;
			}
			sort(all(cons));
			reverse(all(cons));
			
			vector<pair<int,int>> ques;
			vector<int> changes;
			
			for(int j = last; j < i; j ++) {
				if(type[j] == 1) {
					changes.push_back(j);
				}
				else {
					ques.push_back({val[j] , j});
				}
			}
//			cout << "QUES\n";
			sort(all(ques));
			for(auto x: changes) {
				prank[x] = h[pos[x]];
			}
			vector<int> st;
			for(auto to: ques) {
				while(cons.size() && cons.back().F < to.F) {
					st.push_back(cons.back().S);
					upd(cons.back().S);
					cons.pop_back();
				}
				for(auto x: changes) {
					if(x > to.S) break;
					h[pos[x]] = val[x];
				}
				for(auto x: changes) {
					if(h[pos[x]] < to.F) {
						upd(pos[x]);
					}
				}
				
				ans[to.S] = t[1].pix;
				for(auto x: changes) {
					upd(pos[x] , 0);
					h[pos[x]] = prank[x];
				}
			}
			for(auto x: changes) {
				h[pos[x]] = val[x];
			}
			for(auto to: st) {
				upd(to , 0);
			}
			last = i;
		}
		if(i == q) break;
		
		cin >> type[i];
		if(type[i] == 1) {
			cin >> pos[i] >> val[i];
			u[pos[i]] = 1;
		}
		else {
			cin >> val[i];
		}
	}
	for(int i = 0; i < q; i ++) {
		if(type[i] == 2)
			cout << ans[i] << '\n';
	}
}
/*
*/
main() {
	ios;
    int tt = 1;
    // cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message

game.cpp: In function 'void upd(int, int, int, int, int)':
game.cpp:30:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int um = ul+ur >> 1;
      |           ~~^~~
game.cpp: At global scope:
game.cpp:126:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  126 | main() {
      |      ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 492 KB Output is correct
3 Correct 15 ms 492 KB Output is correct
4 Correct 15 ms 492 KB Output is correct
5 Correct 15 ms 492 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 492 KB Output is correct
3 Correct 15 ms 492 KB Output is correct
4 Correct 15 ms 492 KB Output is correct
5 Correct 15 ms 492 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Execution timed out 1086 ms 6904 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 15 ms 492 KB Output is correct
3 Correct 15 ms 492 KB Output is correct
4 Correct 15 ms 492 KB Output is correct
5 Correct 15 ms 492 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Execution timed out 1086 ms 6904 KB Time limit exceeded
9 Halted 0 ms 0 KB -