oj.uz

Submission #505361

# Submission time Handle Problem Language Result Execution time Memory
505361 2022-01-11T04:41:42 Z mansur Simple game (IZhO17_game) C++17
100 / 100
 212 ms 19840 KB 
#include<bits/stdc++.h>	
 
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")

//01001101 01100001 01101011 01101000 01100001  01100111 01100001 01111001 

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()                                                                   
#define ld double
#define ull unsigned long long
#define ff first                                         
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>                          
#define E exit (0)
#define int long long
 
const int inf = 1e9, N = 1e6 + 1, mod = 998244353;                    

vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int t[4 * N];

void update(int u, int tl, int tr, int l, int r, int val) {
	if (tl > r || tr < l) return;
	if (tl >= l && tr <= r) {
		t[u] += val;
		return;
	}
	int mid = (tl + tr) / 2;
	update(u * 2, tl, mid, l, r, val);
	update(u * 2 + 1, mid + 1, tr, l, r, val);
}

int get(int u, int tl, int tr, int pos) {
	if (tl == tr) return t[u];
	int mid = (tl + tr) / 2;
	if (pos <= mid) return get(u * 2, tl, mid, pos) + t[u];
	return get(u * 2 + 1, mid + 1, tr, pos) + t[u];
}

main() {                                                         
	//freopen("cowrect.in", "r", stdin);                                                                                     
	//freopen("cowrect.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(NULL);                                                                                        
	cin.tie(NULL);  
	int n, m;
	cin >> n >> m;
	int y[n + 1];
	for (int i = 1; i <= n; i++) {
		cin >> y[i];
		if (i > 1) {
			update(1, 1, N - 1, min(y[i - 1], y[i]), max(y[i - 1], y[i]), 1);
		}
	}
	while (m--) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int i, val;
			cin >> i >> val;
			if (i > 1)
				update(1, 1, N - 1, min(y[i - 1], y[i]), max(y[i - 1], y[i]), -1);
			if (i < n) 
				update(1, 1, N - 1, min(y[i + 1], y[i]), max(y[i + 1], y[i]), -1);
			y[i] = val;
			if (i > 1)
				update(1, 1, N - 1, min(y[i - 1], y[i]), max(y[i - 1], y[i]), 1);
			if (i < n) 
				update(1, 1, N - 1, min(y[i + 1], y[i]), max(y[i + 1], y[i]), 1);
		}else {
			int h;
			cin >> h;
			cout << get(1, 1, N - 1, h) << nl;
		}
	}
}

Compilation message

game.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      | 
game.cpp:9: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    9 | #pragma comment(linker, "/stack:200000000")
      | 
game.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main() {
      | ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 6 ms 9164 KB Output is correct
4 Correct 8 ms 9292 KB Output is correct
5 Correct 5 ms 9292 KB Output is correct
6 Correct 6 ms 9548 KB Output is correct
7 Correct 2 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 6 ms 9164 KB Output is correct
4 Correct 8 ms 9292 KB Output is correct
5 Correct 5 ms 9292 KB Output is correct
6 Correct 6 ms 9548 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 41 ms 1552 KB Output is correct
9 Correct 104 ms 19664 KB Output is correct
10 Correct 114 ms 19664 KB Output is correct
11 Correct 58 ms 1860 KB Output is correct
12 Correct 68 ms 3544 KB Output is correct
13 Correct 97 ms 3128 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 6 ms 9164 KB Output is correct
4 Correct 8 ms 9292 KB Output is correct
5 Correct 5 ms 9292 KB Output is correct
6 Correct 6 ms 9548 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 41 ms 1552 KB Output is correct
9 Correct 104 ms 19664 KB Output is correct
10 Correct 114 ms 19664 KB Output is correct
11 Correct 58 ms 1860 KB Output is correct
12 Correct 68 ms 3544 KB Output is correct
13 Correct 97 ms 3128 KB Output is correct
14 Correct 205 ms 19840 KB Output is correct
15 Correct 193 ms 19608 KB Output is correct
16 Correct 192 ms 19648 KB Output is correct
17 Correct 212 ms 19684 KB Output is correct
18 Correct 179 ms 19652 KB Output is correct