oj.uz

Submission #37235

# Submission time Handle Problem Language Result Execution time Memory
37235 2017-12-22T19:02:24 Z temurbek_khujaev Simple game (IZhO17_game) C++11
100 / 100
 299 ms 54100 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <iostream>
#include <math.h>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <string.h>
#include <cstring>
#include <queue>
#include <iomanip>
#include <istream>
#include <map>
#include <list>
#include <stack>
#include <numeric>
#include <ostream>
#include <set>
#include <cassert>
#include <sstream>
#include <string>
#include <utility>
#include <stdio.h>
#include <vector>
using namespace std;
#define dout if (debug) cout
#define PB push_back
#define MP make_pair
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int((x.size())))
typedef long double ld;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<PII> VPI;
#define REP(i,a,n) for (int i=a;i<n;i++)
#define db(x) cerr << #x << " = " << x << endl
#define PER(i,a,n) for (int i=n-1;i>=a;i--)
const int INF = 1000000404;
const ll MOD = 1000000007ll;
const ld PI = acos(-1.0);
const ld EPS = 1e-9;
template <typename t1, typename t2> inline void upmax(t1 &a, t2 b) { a = max(a, (t1)b); }
template <typename t1, typename t2> inline void upmin(t1 &a, t2 b) { a = min(a, (t1)b); }
template <typename T>inline T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template <typename T>inline T lcm(T a, T b) { return a*(b / gcd(a, b)); }
template <typename T>inline T sqr(T a) { return a*a; }
template <typename T>inline bool pal(T &x)
{
	int n = SZ(x); REP(i, 0, n / 2) { if (x[i] != x[n - i - 1]) return 0; }return 1;
}
template <typename T>inline void rev(T &x) { int n = SZ(x); REP(i, 0, n / 2) swap(x[i], x[n - i - 1]); }
int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
inline ll mp(ll a, ll b) { return (a << 31) + b; }
class compare{
public:
	bool operator()(const int a, const int b) const {
		return 1;
	}
};
int SQ = 400;

#define debug 1
#define N 1111111
int t[N * 4];
int p[N * 4];
int h[N * 4];

void update(int l, int r, int delta, int v = 1, int tl = 1, int tr = 1000000) {
	if (l > tr || r < tl) return;
	if (l <= tl&&tr <= r) {
		t[v] += delta;
		return;
	}
	int tm = (tl + tr) >> 1;
	update(l, r, delta, v + v, tl, tm);
	update(l, r, delta, v + v + 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = 1000000) {
	if (tl == tr) return t[v];
	int tm = (tl + tr) >> 1;
	if (pos <= tm) return t[v] + get(pos, v + v, tl, tm);
	else return t[v] + get(pos, v + v + 1, tm + 1, tr);
}

void solve()
{
	int n, m;
	cin >> n >> m;
	REP(i, 1, n + 1) scanf("%d",h+i);
	REP(i, 2, n + 1) {
		int a = h[i - 1];
		int b = h[i];
		update(min(a, b), max(a, b), 1);
	}
	REP(i, 0, m) {
		int type, pos, val, H;
		scanf("%d",&type);
		if (type == 1) {
			scanf("%d%d",&pos,&val);
			int a = h[pos - 1];
			int b = h[pos];
			int c = h[pos + 1];
			if (pos != 1) {
				update(min(a, b), max(a, b), -1);
				update(min(a, val), max(a, val), 1);
			}
			if (pos != n) {
				update(min(c, b), max(c, b), -1);
				update(min(c, val), max(c, val), 1);
			}
			h[pos] = val;
		}
		else {
			scanf("%d",&H);
          	printf("%d\n",get(H));
		}
	}

}

int main()
{

	int t = 1;
	//cin>>t;

	while (t--) {	
		solve();
	};


	//getchar();
	//	getchar();
	return 0;
}

Compilation message

game.cpp: In function 'void solve()':
game.cpp:96:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REP(i, 1, n + 1) scanf("%d",h+i);
                                  ^
game.cpp:104:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
                    ^
game.cpp:106:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&pos,&val);
                           ^
game.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&H);
                  ^

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 54100 KB Output is correct
2 Correct 0 ms 54100 KB Output is correct
3 Correct 3 ms 54100 KB Output is correct
4 Correct 0 ms 54100 KB Output is correct
5 Correct 6 ms 54100 KB Output is correct
6 Correct 3 ms 54100 KB Output is correct
7 Correct 0 ms 54100 KB Output is correct
8 Correct 69 ms 54100 KB Output is correct
9 Correct 183 ms 54100 KB Output is correct
10 Correct 143 ms 54100 KB Output is correct
11 Correct 73 ms 54100 KB Output is correct
12 Correct 126 ms 54100 KB Output is correct
13 Correct 63 ms 54100 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 54100 KB Output is correct
2 Correct 0 ms 54100 KB Output is correct
3 Correct 3 ms 54100 KB Output is correct
4 Correct 0 ms 54100 KB Output is correct
5 Correct 6 ms 54100 KB Output is correct
6 Correct 3 ms 54100 KB Output is correct
7 Correct 0 ms 54100 KB Output is correct
8 Correct 69 ms 54100 KB Output is correct
9 Correct 183 ms 54100 KB Output is correct
10 Correct 143 ms 54100 KB Output is correct
11 Correct 73 ms 54100 KB Output is correct
12 Correct 126 ms 54100 KB Output is correct
13 Correct 63 ms 54100 KB Output is correct
14 Correct 279 ms 54100 KB Output is correct
15 Correct 286 ms 54100 KB Output is correct
16 Correct 269 ms 54100 KB Output is correct
17 Correct 299 ms 54100 KB Output is correct
18 Correct 289 ms 54100 KB Output is correct