oj.uz

Submission #339302

# Submission time Handle Problem Language Result Execution time Memory
339302 2020-12-25T03:39:45 Z boykut Simple game (IZhO17_game) C++14
100 / 100
 607 ms 19564 KB 
#include <iostream>
//#include <fstream>
#include <cmath>
#include <iomanip>
#include <set>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

//#define int long long
#define pb push_back
#define sc second
#define fr first

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define mt make_tuple
#define all(a) (a).begin(),(a).end()
const int MAXN = 0, inf = 2e9;

int sm[4000100], tadd[4000100];
int N = 1000100;

void push(int v, int vl, int vr) {
   if (tadd[v] != 0) {
      sm[v] += tadd[v] * (vr - vl + 1);
      if (vl != vr) {
         tadd[v+v+1] += tadd[v];
         tadd[v+v+2] += tadd[v];
      }
      tadd[v] = 0;
   }
};
int rsq(int v, int vl, int vr, int l, int r) {
   push(v, vl, vr);
   if (r < vl || vr < l)
      return 0;
   if (l <= vl && vr <= r) {
      return sm[v];
   }
   int vm = (vl + vr) / 2;
   int ff = rsq(v+v+1, vl, vm, l, r);
   int ss = rsq(v+v+2, vm+1, vr, l, r);
   return ff + ss;
};
void add(int v, int vl, int vr, int l, int r, int val) {
   push(v, vl, vr);
   if (r < vl || vr < l)
      return;
   if (l <= vl && vr <= r) {
      tadd[v] = val;
      push(v, vl, vr);
      return;
   }
   int vm = (vl + vr) / 2;
   add(v+v+1, vl, vm, l, r, val);
   add(v+v+2, vm+1, vr, l, r, val);
};

void inc(int l, int r, int val) {
   add(0, 0, N - 1, min(l, r), max(l, r), val);
}

void solve() {
   int n, q;
   cin >> n >> q;
   vector <int> h(n);
   
   for (int i = 0; i < n; i++) {
      cin >> h[i];
      if (i) {
         inc(h[i], h[i - 1], +1);
      }
   }
   
   for (int tmp = q, t; tmp--;) {
      cin >> t;
      if (t == 1) {
         int pos, val;
         cin >> pos >> val;
         pos--;
         if (pos - 1 >=0) inc(h[pos], h[pos - 1], -1);
         if (pos + 1 < n) inc(h[pos], h[pos + 1], -1);
         h[pos] = val;
         if (pos - 1 >=0) inc(h[pos], h[pos - 1], +1);
         if (pos + 1 < n) inc(h[pos], h[pos + 1], +1);
      } else {
         int H;
         cin >> H;
         cout << rsq(0, 0, N - 1, H, H) << '\n';
      }
   }
   return;
}

signed main() {
   //IOS;
   int q = 1;
   //cin >> q;
   while (q --) {
      solve();
   }
   return 0;
}

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 15084 KB Output is correct
3 Correct 14 ms 14828 KB Output is correct
4 Correct 14 ms 14956 KB Output is correct
5 Correct 15 ms 15084 KB Output is correct
6 Correct 14 ms 14976 KB Output is correct
7 Correct 12 ms 12780 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 15 ms 15084 KB Output is correct
3 Correct 14 ms 14828 KB Output is correct
4 Correct 14 ms 14956 KB Output is correct
5 Correct 15 ms 15084 KB Output is correct
6 Correct 14 ms 14976 KB Output is correct
7 Correct 12 ms 12780 KB Output is correct
8 Correct 340 ms 1772 KB Output is correct
9 Correct 516 ms 19564 KB Output is correct
10 Correct 520 ms 19436 KB Output is correct
11 Correct 336 ms 1772 KB Output is correct
12 Correct 403 ms 3288 KB Output is correct
13 Correct 454 ms 19308 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 15 ms 15084 KB Output is correct
3 Correct 14 ms 14828 KB Output is correct
4 Correct 14 ms 14956 KB Output is correct
5 Correct 15 ms 15084 KB Output is correct
6 Correct 14 ms 14976 KB Output is correct
7 Correct 12 ms 12780 KB Output is correct
8 Correct 340 ms 1772 KB Output is correct
9 Correct 516 ms 19564 KB Output is correct
10 Correct 520 ms 19436 KB Output is correct
11 Correct 336 ms 1772 KB Output is correct
12 Correct 403 ms 3288 KB Output is correct
13 Correct 454 ms 19308 KB Output is correct
14 Correct 606 ms 19564 KB Output is correct
15 Correct 607 ms 19564 KB Output is correct
16 Correct 595 ms 19436 KB Output is correct
17 Correct 606 ms 19548 KB Output is correct
18 Correct 599 ms 19564 KB Output is correct