oj.uz

Submission #38980

# Submission time Handle Problem Language Result Execution time Memory
38980 2018-01-08T18:38:45 Z yerkimbekov Simple game (IZhO17_game) C++14
100 / 100
 716 ms 96712 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[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

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.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 96712 KB Output is correct
2 Correct 6 ms 96712 KB Output is correct
3 Correct 9 ms 96712 KB Output is correct
4 Correct 13 ms 96712 KB Output is correct
5 Correct 6 ms 96712 KB Output is correct
6 Correct 13 ms 96712 KB Output is correct
7 Correct 3 ms 96712 KB Output is correct
8 Correct 123 ms 96712 KB Output is correct
9 Correct 316 ms 96712 KB Output is correct
10 Correct 299 ms 96712 KB Output is correct
11 Correct 93 ms 96712 KB Output is correct
12 Correct 156 ms 96712 KB Output is correct
13 Correct 129 ms 96712 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 96712 KB Output is correct
2 Correct 6 ms 96712 KB Output is correct
3 Correct 9 ms 96712 KB Output is correct
4 Correct 13 ms 96712 KB Output is correct
5 Correct 6 ms 96712 KB Output is correct
6 Correct 13 ms 96712 KB Output is correct
7 Correct 3 ms 96712 KB Output is correct
8 Correct 123 ms 96712 KB Output is correct
9 Correct 316 ms 96712 KB Output is correct
10 Correct 299 ms 96712 KB Output is correct
11 Correct 93 ms 96712 KB Output is correct
12 Correct 156 ms 96712 KB Output is correct
13 Correct 129 ms 96712 KB Output is correct
14 Correct 623 ms 96712 KB Output is correct
15 Correct 629 ms 96712 KB Output is correct
16 Correct 649 ms 96712 KB Output is correct
17 Correct 629 ms 96712 KB Output is correct
18 Correct 716 ms 96712 KB Output is correct