oj.uz

Submission #38978

# Submission time Handle Problem Language Result Execution time Memory
38978 2018-01-08T18:36:43 Z yerkimbekov Simple game (IZhO17_game) C++14
22 / 100
 59 ms 97180 KB 
/*
ID: simpgoo1
TASK: 
LANG: C++14            
*/
// timus 219263UI
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <ctime>
#include <queue>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;

#define y1 needtrainharder
#define F first
#define S second
#define gg exit(0)
#define sz() size()
#define pb push_back
#define mp make_pair
#define skip continue
#define all(x) x.begin(), x.end()
#define boost ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define file(s,x) if(x == 1)freopen(s".in","r",stdin),freopen(s".out","w",stdout);
#define task "sorting"

const int INF = 1e9 + 100;  
const ll INFLL = 1e18 + 100;  
const double EPS = 1e-10;
const int MAXN = 5e5 + 100; 
const int P = 51;
const int mod = 1e9 + 7;

ll n, m;

ll t[1005005 * 6], h[100005], add[1005005 * 6];

void push(ll v, ll tl, ll tr){
  if(add[v] != 0){
    if(tl != tr){
      add[v + v] += add[v];
      add[v + v + 1] += add[v];
    }
    t[v] += add[v];
    add[v] = 0;
  } 
}

void upd(ll l, ll r, ll val, ll v = 1, ll tl = 1, ll tr = 1000000){
  push(v, tl, tr);
  if(l > tr || r < tl)
    return;
  if(l <= tl && tr <= r){
    add[v] += val;
    push(v, tl, tr);
    return;
  }
  ll tm = (tl + tr) >> 1;
  push(v, tl, tr);
  upd(l, r, val, v + v, tl, tm);
  push(v, tl, tr);
  upd(l, r, val, v + v + 1, tm + 1, tr);
  push(v, tl, tr);
}

ll get(ll h, ll v = 1, ll tl = 1, ll tr = 1000000){
  push(v, tl, tr);
  if( tl == tr ){
    return t[v];
  }
  push(v, tl, tr);
  ll tm = (tl + tr) >> 1;
  if(h <= tm)
    return get(h, v + v, tl, tm);
  else
    return get(h, v + v + 1, tm + 1, tr);
}

int main(){ 

  boost; 

  srand(time(NULL));

  if(fopen(task".in", "r")){  
    freopen(task".in", "r", stdin);
    freopen(task".out","w",stdout); 
  }

  cin >> n >> m;
  for(ll i = 1; i <= n; ++i){
    cin >> h[i];
  }
  for(ll i = 2; i <= n; ++i){
    upd(min(h[i], h[i - 1]), max(h[i-1] , h[i]), 1);
  }
  for(ll i = 1, type, l, r; i <= m; ++i){
    cin >> type;
    if(type == 1){
      cin >> l >> r;
      if(l + 1 <= n)
        upd(min( h[l], h[l + 1] ), max( h[l], h[l + 1] ), -1);
      if(l - 1 >= 1)
        upd(min( h[l], h[l - 1] ),max( h[l], h[l - 1] ), -1);
      h[l] = r;
      if(l + 1 <= n)
        upd(min( h[l], h[l + 1] ), max( h[l], h[l + 1] ), 1);
      if(l - 1 >= 1)
        upd(min( h[l], h[l - 1] ),max( h[l], h[l - 1] ), 1);
    }else{
      cin >> l;
      cout << get(l) << '\n';
    }
  }

  return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:98:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(task".in", "r", stdin);
                                   ^
game.cpp:99:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(task".out","w",stdout); 
                                   ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 97180 KB Output is correct
2 Correct 9 ms 97180 KB Output is correct
3 Correct 16 ms 97180 KB Output is correct
4 Correct 13 ms 97180 KB Output is correct
5 Correct 3 ms 97180 KB Output is correct
6 Correct 9 ms 97180 KB Output is correct
7 Correct 3 ms 97180 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 97180 KB Output is correct
2 Correct 9 ms 97180 KB Output is correct
3 Correct 16 ms 97180 KB Output is correct
4 Correct 13 ms 97180 KB Output is correct
5 Correct 3 ms 97180 KB Output is correct
6 Correct 9 ms 97180 KB Output is correct
7 Correct 3 ms 97180 KB Output is correct
8 Runtime error 59 ms 97180 KB Execution killed because of forbidden syscall writev (20)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 97180 KB Output is correct
2 Correct 9 ms 97180 KB Output is correct
3 Correct 16 ms 97180 KB Output is correct
4 Correct 13 ms 97180 KB Output is correct
5 Correct 3 ms 97180 KB Output is correct
6 Correct 9 ms 97180 KB Output is correct
7 Correct 3 ms 97180 KB Output is correct
8 Runtime error 59 ms 97180 KB Execution killed because of forbidden syscall writev (20)
9 Halted 0 ms 0 KB -