Submission #988757

# Submission time Handle Problem Language Result Execution time Memory
988757 2024-05-26T00:07:10 Z bigo Horses (IOI15_horses) C++14
34 / 100
1500 ms 524288 KB
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#define all(a) a.begin(), a.end()
#define rep(i,s,e) for(ll i=s;i<e;i++)
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 1e18;
typedef complex<double> cd;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
const ll mod1 = 1e9 + 9;
const ll mod2 = 998244353;
const ll mac = 31;
const ll MAXN = 4e5 + 2;
typedef vector<int> vi;
typedef vector<vi> vvi;



ll cef(ll a, ll b) {
	ll val;
	if (ll(a) * ll(b) >= 1e9)
		val = 0;
	else
		val = a*b;
	return val;
}

struct seg {
	ll l, r, mid, val=1;
	seg* lp, * rp;
	seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
		if (l < r) {
			lp = new seg(l, mid);
			rp = new seg(mid+1,r);
		}
	}
	void pull() {
		val = cef(lp->val, rp->val);
	}
	void upd(ll i,ll x) {
		if (l == r) {
			val = x;
			return;
		}
		if (i <= mid) lp->upd(i, x);
		else rp->upd(i, x);
		pull();
	}
	ll que(ll a, ll b) {
		if (a <= l and r <= b) return val;
		if (a > r or l > b) return 1;
		return cef(lp->que(a, b),rp->que(a, b));
	}
};

int n;
vi x, y;

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(n);
	y.resize(n);
	rep(i, 0, n) x[i] = X[i], y[i] = Y[i];
	pair<ll, ll>ans = {0,(x[0]*y[0])%mod};
	ll c = x[0];
	seg segx(0, n - 1);
	rep(i, 1, n) {
		segx.upd(i, x[i]);
		c *= x[i];
		c %= mod;
		ll t = cef(segx.que(ans.first + 1, i), y[i]);
		if (t == 0 or t >= y[ans.first])
			ans = { i,(c * y[i]) % mod };
	}
	return ans.second;
}

int updateX(int pos, int val) {
	x[pos] = val;
	pair<ll, ll>ans = { 0,(x[0] * y[0]) % mod };
	ll c = x[0];
	seg segx(0, n - 1);
	rep(i, 1, n) {
		segx.upd(i, x[i]);
		c *= x[i];
		c %= mod;
		ll t = cef(segx.que(ans.first + 1, i), y[i]);
		if (t == 0 or t >= y[ans.first])
			ans = { i,(c * y[i]) % mod };
	}
	return ans.second;
}

int updateY(int pos, int val) {
	y[pos] = val;
	pair<ll, ll>ans = { 0,(x[0] * y[0]) % mod };
	ll c = x[0];
	seg segx(0, n - 1);
	rep(i, 1, n) {
		segx.upd(i, x[i]);
		c *= x[i];
		c %= mod;
		ll t = cef(segx.que(ans.first + 1, i), y[i]);
		if (t == 0 or t >= y[ans.first])
			ans = { i,(c * y[i]) % mod };
	}
	return ans.second;
}

Compilation message

horses.cpp: In function 'll cef(ll, ll)':
horses.cpp:25:12: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   25 |  if (ll(a) * ll(b) >= 1e9)
      |      ~~~~~~^~~~~~~
horses.cpp: In constructor 'seg::seg(ll, ll)':
horses.cpp:35:15: warning: declaration of 'r' shadows a member of 'seg' [-Wshadow]
   35 |  seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
      |            ~~~^
horses.cpp:33:8: note: shadowed declaration is here
   33 |  ll l, r, mid, val=1;
      |        ^
horses.cpp:35:9: warning: declaration of 'l' shadows a member of 'seg' [-Wshadow]
   35 |  seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
      |      ~~~^
horses.cpp:33:5: note: shadowed declaration is here
   33 |  ll l, r, mid, val=1;
      |     ^
horses.cpp: In constructor 'seg::seg(ll, ll)':
horses.cpp:35:15: warning: declaration of 'r' shadows a member of 'seg' [-Wshadow]
   35 |  seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
      |            ~~~^
horses.cpp:33:8: note: shadowed declaration is here
   33 |  ll l, r, mid, val=1;
      |        ^
horses.cpp:35:9: warning: declaration of 'l' shadows a member of 'seg' [-Wshadow]
   35 |  seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
      |      ~~~^
horses.cpp:33:5: note: shadowed declaration is here
   33 |  ll l, r, mid, val=1;
      |     ^
horses.cpp: In constructor 'seg::seg(ll, ll)':
horses.cpp:35:15: warning: declaration of 'r' shadows a member of 'seg' [-Wshadow]
   35 |  seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
      |            ~~~^
horses.cpp:33:8: note: shadowed declaration is here
   33 |  ll l, r, mid, val=1;
      |        ^
horses.cpp:35:9: warning: declaration of 'l' shadows a member of 'seg' [-Wshadow]
   35 |  seg(ll l, ll r): l(l), r(r), mid((l + r) / 2) {
      |      ~~~^
horses.cpp:33:5: note: shadowed declaration is here
   33 |  ll l, r, mid, val=1;
      |     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:79:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return ans.second;
      |         ~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:95:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |  return ans.second;
      |         ~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:111:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |  return ans.second;
      |         ~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:54:33: warning: 'segx.seg::rp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (a <= l and r <= b) return val;
      |                                 ^~~
horses.cpp:86:6: note: 'segx.seg::rp' was declared here
   86 |  seg segx(0, n - 1);
      |      ^~~~
horses.cpp:54:33: warning: 'segx.seg::lp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (a <= l and r <= b) return val;
      |                                 ^~~
horses.cpp:86:6: note: 'segx.seg::lp' was declared here
   86 |  seg segx(0, n - 1);
      |      ^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:54:33: warning: 'segx.seg::rp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (a <= l and r <= b) return val;
      |                                 ^~~
horses.cpp:102:6: note: 'segx.seg::rp' was declared here
  102 |  seg segx(0, n - 1);
      |      ^~~~
horses.cpp:54:33: warning: 'segx.seg::lp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (a <= l and r <= b) return val;
      |                                 ^~~
horses.cpp:102:6: note: 'segx.seg::lp' was declared here
  102 |  seg segx(0, n - 1);
      |      ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:54:33: warning: 'segx.seg::rp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (a <= l and r <= b) return val;
      |                                 ^~~
horses.cpp:70:6: note: 'segx.seg::rp' was declared here
   70 |  seg segx(0, n - 1);
      |      ^~~~
horses.cpp:54:33: warning: 'segx.seg::lp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   if (a <= l and r <= b) return val;
      |                                 ^~~
horses.cpp:70:6: note: 'segx.seg::lp' was declared here
   70 |  seg segx(0, n - 1);
      |      ^~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 352 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 356 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 237 ms 125724 KB Output is correct
24 Correct 235 ms 125456 KB Output is correct
25 Correct 212 ms 125524 KB Output is correct
26 Correct 218 ms 125592 KB Output is correct
27 Correct 236 ms 125680 KB Output is correct
28 Correct 218 ms 125388 KB Output is correct
29 Correct 208 ms 125448 KB Output is correct
30 Correct 209 ms 125456 KB Output is correct
31 Correct 240 ms 125520 KB Output is correct
32 Correct 256 ms 125520 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1544 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 230 ms 125624 KB Output is correct
24 Correct 227 ms 125520 KB Output is correct
25 Correct 222 ms 125476 KB Output is correct
26 Correct 218 ms 125524 KB Output is correct
27 Correct 236 ms 125520 KB Output is correct
28 Correct 216 ms 125468 KB Output is correct
29 Correct 211 ms 125560 KB Output is correct
30 Correct 208 ms 125520 KB Output is correct
31 Correct 237 ms 125780 KB Output is correct
32 Correct 248 ms 125540 KB Output is correct
33 Execution timed out 1586 ms 513412 KB Time limit exceeded
34 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 228 ms 125472 KB Output is correct
24 Correct 230 ms 125520 KB Output is correct
25 Correct 216 ms 125696 KB Output is correct
26 Correct 214 ms 125520 KB Output is correct
27 Correct 234 ms 125520 KB Output is correct
28 Correct 221 ms 125460 KB Output is correct
29 Correct 211 ms 125560 KB Output is correct
30 Correct 212 ms 125504 KB Output is correct
31 Correct 241 ms 125828 KB Output is correct
32 Correct 246 ms 125524 KB Output is correct
33 Runtime error 1489 ms 524288 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -