oj.uz

Submission #38975

# Submission time Handle Problem Language Result Execution time Memory
38975 2018-01-08T18:15:50 Z yerkimbekov Simple game (IZhO17_game) C++14
0 / 100
 0 ms 33820 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;

int n, m;

int t[1000005 * 4], h[100005], add[1000005 * 4];

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

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

int get(int h, int v = 1, int tl = 1, int tr = n){
  push(v, tl, tr);
  if( tl == tr ){
    return t[v];
  }
  push(v, tl, tr);
  int tm = (tl + tr) >> 1;
  if(tm <= h)
    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(int i = 1; i <= n; ++i){
    cin >> h[i];
  }
  for(int i = 2; i <= n; ++i){
    upd(min(h[i], h[i - 1]), max(h[i-1] , h[i]), 1);
  }
  for(int 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:97: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:98: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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33820 KB Output is correct
2 Incorrect 0 ms 33820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33820 KB Output is correct
2 Incorrect 0 ms 33820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 33820 KB Output is correct
2 Incorrect 0 ms 33820 KB Output isn't correct
3 Halted 0 ms 0 KB -