Submission #38980

#	Time	Username	Problem	Language	Result	Execution time	Memory
38980		yerkimbekov	Simple game (IZhO17_game)	C++14	100 / 100	716 ms	96712 KiB

game

/*
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[1000010 * 6], h[100005], add[1000010 * 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 - 6){
  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 - 6){
  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;
  scanf("%lld %lld", &n, &m);
  for(ll i = 1; i <= n; ++i){
    scanf("%lld", &h[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;
    scanf("%lld", &type);
    if(type == 1){
      scanf("%lld %lld", &l, &r);
      // 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{
      scanf("%lld", &l);
      // cin >> l;
      printf("%lld\n", get(l));
      // cout << get(l) << '\n';
    }
  }

  return 0;
}

Compilation message (stderr)

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); 
                                   ^
game.cpp:103:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &n, &m);
                             ^
game.cpp:105:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &h[i]);
                         ^
game.cpp:113:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &type);
                         ^
game.cpp:115:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld %lld", &l, &r);
                                 ^
game.cpp:127:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &l);
                        ^

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51