답안 #785236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785236	2023-07-17T07:28:32 Z	NothingXD	말 (IOI15_horses)	C++17	77 / 100	1500 ms	29948 KB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << " ";
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;

int n;
ll x[maxn], y[maxn];
ll dp[maxn << 2][2];
bool of[maxn << 2];

int find(int v, int l, int r, int tmp){
	if (!of[v] && 1ll * tmp * dp[v][1] < mod) return -1;
	if (l + 1 == r) return l;
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	int res = find(rc, mid, r, tmp);
	if (res == -1){
		tmp *= dp[rc][1];
		res = find(lc, l, mid, tmp);
	}
	return res;
}

void build2(int v, int l, int r){
	if (l + 1 == r){
		dp[v][0] = x[l] * y[l];
		dp[v][1] = x[l];
		return;
	}
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	build2(lc, l, mid);
	build2(rc, mid, r);
	dp[v][0] = max(dp[lc][0], dp[lc][1] * dp[rc][0]);
	dp[v][1] = dp[lc][1] * dp[rc][1];
	if (dp[v][1] >= mod || of[lc] || of[rc]) of[v] = true;
	dp[v][1] %= mod;
}

void change2(int v, int l, int r, int idx){
	if (l + 1 == r){
		dp[v][0] = x[l] * y[l];
		dp[v][1] = x[l];
		return;
	}
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	if (idx < mid) change2(lc, l, mid, idx);
	else change2(rc, mid, r, idx);
	dp[v][0] = max(dp[lc][0], dp[lc][1] * dp[rc][0]);
	dp[v][1] = dp[lc][1] * dp[rc][1];
	if (dp[v][1] >= mod || of[lc] || of[rc]) of[v] = true;
	dp[v][1] %= mod;
}

pll get2(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return {1, 1};
	if (ql <= l && r <= qr) return MP(dp[v][0], dp[v][1]);
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	pll a = get2(lc, l, mid, ql, qr);
	pll b = get2(rc, mid, r, ql, qr);
	return MP(max(a.F, a.S * b.F), a.S * b.S % mod);
}

int Calc(){
	int idx = find(1, 0, n, 1);
	if (idx == -1) idx = 0;
	int tmp = get2(1, 0, n, 0, idx+1).S;
	ll tmp2 = max(y[idx], get2(1, 0, n, idx+1, n).F) % mod;
	return 1ll * tmp * tmp2 % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++){
		x[i] = X[i];
		y[i] = Y[i];
	}
	build2(1, 0, n);
	return Calc();
}

int updateX(int pos, int val) {
	x[pos] = val;
	change2(1, 0, n, pos);
	return Calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	change2(1, 0, n, pos);
	return Calc();
}

Compilation message

horses.cpp: In function 'int find(int, int, int, int)':
horses.cpp:42:7: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   42 |   tmp *= dp[rc][1];
      |   ~~~~^~~~~~~~~~~~
horses.cpp: In function 'int Calc()':
horses.cpp:22:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 | #define S second
      |           ^
horses.cpp:96:36: note: in expansion of macro 'S'
   96 |  int tmp = get2(1, 0, n, 0, idx+1).S;
      |                                    ^
horses.cpp:98:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  return 1ll * tmp * tmp2 % mod;
      |         ~~~~~~~~~~~~~~~~~^~~~~

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	300 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	2 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	4 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	29408 KB	Output is correct
2	Correct	163 ms	29948 KB	Output is correct
3	Correct	143 ms	29860 KB	Output is correct
4	Correct	142 ms	29860 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	4 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	46 ms	28628 KB	Output is correct
34	Correct	44 ms	28668 KB	Output is correct
35	Correct	66 ms	28988 KB	Output is correct
36	Correct	73 ms	29020 KB	Output is correct
37	Correct	41 ms	28576 KB	Output is correct
38	Correct	35 ms	28568 KB	Output is correct
39	Correct	41 ms	28372 KB	Output is correct
40	Correct	379 ms	29060 KB	Output is correct
41	Correct	32 ms	28544 KB	Output is correct
42	Correct	31 ms	28532 KB	Output is correct
43	Correct	41 ms	28912 KB	Output is correct
44	Correct	42 ms	28876 KB	Output is correct

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	2 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	4 ms	396 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	97 ms	29500 KB	Output is correct
34	Correct	188 ms	29936 KB	Output is correct
35	Correct	131 ms	29936 KB	Output is correct
36	Correct	143 ms	29900 KB	Output is correct
37	Correct	45 ms	28620 KB	Output is correct
38	Correct	44 ms	28564 KB	Output is correct
39	Correct	65 ms	29060 KB	Output is correct
40	Correct	66 ms	29104 KB	Output is correct
41	Correct	35 ms	28500 KB	Output is correct
42	Correct	46 ms	28500 KB	Output is correct
43	Correct	31 ms	28480 KB	Output is correct
44	Correct	388 ms	29028 KB	Output is correct
45	Correct	31 ms	28524 KB	Output is correct
46	Correct	35 ms	28528 KB	Output is correct
47	Correct	42 ms	28900 KB	Output is correct
48	Correct	44 ms	28888 KB	Output is correct
49	Correct	140 ms	29928 KB	Output is correct
50	Correct	143 ms	29896 KB	Output is correct
51	Correct	142 ms	29864 KB	Output is correct
52	Correct	128 ms	29900 KB	Output is correct
53	Correct	122 ms	29440 KB	Output is correct
54	Correct	105 ms	29396 KB	Output is correct
55	Correct	80 ms	28688 KB	Output is correct
56	Execution timed out	1586 ms	29296 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-