oj.uz

Submission #332025

# Submission time Handle Problem Language Result Execution time Memory
332025 2020-12-01T08:46:31 Z Valera_Grinenko Simple game (IZhO17_game) C++17
100 / 100
 408 ms 20256 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e6 + 42, H = 1e6 + 42;
int t[N];
void update (int v, int tl, int tr, int l, int r, int add) {
	if (l > r)
		return;
	if (l == tl && tr == r)
		t[v] += add;
	else {
		int tm = (tl + tr) / 2;
		update (v*2, tl, tm, l, min(r,tm), add);
		update (v*2+1, tm+1, tr, max(l,tm+1), r, add);
	}
}
int get (int v, int tl, int tr, int pos) {
	if (tl == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		return t[v] + get (v*2, tl, tm, pos);
	else
		return t[v] + get (v*2+1, tm+1, tr, pos);
}
int n, m;
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n >> m;

  vector<int> h(n);

  for(int i = 0; i < n; i++) {
    cin >> h[i];
    if(i) {
      update(1, 0, H - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
    }
  }

	map<int, int> amm;

	for(int i = 1; i < n - 1; i++) amm[h[i]]++;

  while(m--) {
    int t; cin >> t;
    if(t == 2) {
      int ch; cin >> ch;
      cout << get(1, 0, H - 1, ch) - amm[ch] << '\n';
    } else {
      int ci, ch; cin >> ci >> ch;
      ci--;
			if(ci > 0 && ci < n - 1) amm[h[ci]]--;
      if(ci + 1 < n) {
        update(1, 0, H - 1, min(h[ci], h[ci + 1]), max(h[ci], h[ci + 1]), -1);
      }
      if(ci - 1 >= 0) {
        update(1, 0, H - 1, min(h[ci], h[ci - 1]), max(h[ci], h[ci - 1]), -1);
      }
      h[ci] = ch;
      if(ci + 1 < n) {
        update(1, 0, H - 1, min(h[ci], h[ci + 1]), max(h[ci], h[ci + 1]), 1);
      }
      if(ci - 1 >= 0) {
        update(1, 0, H - 1, min(h[ci], h[ci - 1]), max(h[ci], h[ci - 1]), 1);
      }
			if(ci > 0 && ci < n - 1) amm[h[ci]]++;
    }
  }

  return 0;
}
/*

*/

Compilation message

game.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 6636 KB Output is correct
3 Correct 6 ms 6508 KB Output is correct
4 Correct 7 ms 6764 KB Output is correct
5 Correct 7 ms 6636 KB Output is correct
6 Correct 7 ms 6764 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 53 ms 1772 KB Output is correct
9 Correct 260 ms 20256 KB Output is correct
10 Correct 250 ms 20136 KB Output is correct
11 Correct 46 ms 1644 KB Output is correct
12 Correct 126 ms 4460 KB Output is correct
13 Correct 130 ms 7404 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 6636 KB Output is correct
3 Correct 6 ms 6508 KB Output is correct
4 Correct 7 ms 6764 KB Output is correct
5 Correct 7 ms 6636 KB Output is correct
6 Correct 7 ms 6764 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 53 ms 1772 KB Output is correct
9 Correct 260 ms 20256 KB Output is correct
10 Correct 250 ms 20136 KB Output is correct
11 Correct 46 ms 1644 KB Output is correct
12 Correct 126 ms 4460 KB Output is correct
13 Correct 130 ms 7404 KB Output is correct
14 Correct 394 ms 19948 KB Output is correct
15 Correct 399 ms 19948 KB Output is correct
16 Correct 408 ms 20076 KB Output is correct
17 Correct 405 ms 19948 KB Output is correct
18 Correct 389 ms 19948 KB Output is correct