답안 #574108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574108	2022-06-07T19:49:50 Z	perchuts	말 (IOI15_horses)	C++17	100 / 100	206 ms	74860 KB

horses

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const ll inf = 1e9+1ll;
const int mod = 1e9+7;
const int maxn = 5e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

// #include "horses.h"
// construir uma seg com merge: preciso do melhor segmento,
// produtorio do melhor segmento, sufixo dos x's depois do melhor segmento, produtorio de todos os x's do segmento
// merge: ou continuo com o da esquerda, ou continuo com o da direita, ou vou da esquerda pra direita
// (mantenho o y da direita)
// a resposta é automaticamente dada por seg[1].
// cuidado: os valores facilmente passarao de 1e18, entao como estamos comparando apenas com o y (que vai ate 1e9)
// , se o valor passa de 1e9 nao faco update dele mais (apenas pra comparacao, na resposta tem que tirar o mod)

ll x[maxn], y[maxn];
int n;

struct node{
	ll best,bestmod, suf, tot, totmod;
	int idx;
}seg[4*maxn];

node merge(node l,node r){
	node res;

	res.tot = min(inf, l.tot*r.tot), res.totmod = (l.totmod*r.totmod)%mod;

	if(y[l.idx]>l.suf*r.best)res.best = l.best, res.bestmod = l.bestmod,
	res.suf = min(inf, l.suf*r.tot), res.idx = l.idx;

	else res.best = min(l.tot*r.best,inf), res.bestmod = (l.totmod*r.bestmod)%mod,
	res.suf = r.suf, res.idx = r.idx;

	return res;
}

void build(int i,int l,int r){
	if(l==r){
		seg[i].best = min(inf,x[l]*y[l]), seg[i].bestmod = (x[l]*y[l])%mod, seg[i].suf = 1ll,
		seg[i].tot = seg[i].totmod = x[l], seg[i].idx = l;
		return; 
	}
	int md = (l+r)/2;
	build(2*i,l,md), build(2*i+1,md+1,r);
	seg[i] = merge(seg[2*i],seg[2*i+1]);
}

void update(int i,int l,int r,int ind,bool mode,ll d){
	if(l>ind||r<ind)return;
	if(l==r){
		if(mode)x[l] = d;
		else y[l] = d;
		seg[i].best = min(inf,x[l]*y[l]), seg[i].bestmod = (x[l]*y[l])%mod, seg[i].suf = 1ll,
		seg[i].tot = seg[i].totmod = x[l], seg[i].idx = l;
		return; 
		return;
	}
	int md = (l+r)/2;
	update(2*i,l,md,ind,mode,d), update(2*i+1,md+1,r,ind,mode,d);
	seg[i] = merge(seg[2*i],seg[2*i+1]);
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=1;i<=n;++i)x[i] = ll(X[i-1]), y[i] = ll(Y[i-1]);
	build(1,1,n);
	return int(seg[1].bestmod);
}

int updateX(int pos, int val) {	
	update(1,1,n,pos+1,1,ll(val));
	return int(seg[1].bestmod);
}

int updateY(int pos, int val) {
	update(1,1,n,pos+1,0,ll(val));
	return int(seg[1].bestmod);
}


// static char _buffer[1024];
// static int _currentChar = 0;
// static int _charsNumber = 0;
// static FILE *_inputFile, *_outputFile;

// static inline int _read() {
//     if (_charsNumber < 0) {
//         exit(1);
//     }
//     if (!_charsNumber || _currentChar == _charsNumber) {
//         _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
//         _currentChar = 0;
//     }
//     if (_charsNumber <= 0) {
//         return -1;
//     }
//     return _buffer[_currentChar++];
// }

// static inline int _readInt() {
//     int c, x, s;
//     c = _read();
//     while (c <= 32) c = _read();
//     x = 0;
//     s = 1;
//     if (c == '-') {
//         s = -1;
//         c = _read();
//     }
//     while (c > 32) {
//         x *= 10;
//         x += c - '0';
//         c = _read();
//     }
//     if (s < 0) x = -x;
//     return x;
// }


// int main() {
	
// 	int N;cin>>N;

// 	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
// 	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

// 	for (int i = 0; i < N; i++) {
// 		cin>>X[i];
// 	}

// 	for (int i = 0; i < N; i++) {
// 		cin>>Y[i];
// 	}	

// 	cout<<init(N,X,Y)<<endl;
//  	int M;cin>>M;

// 	for (int i = 0; i < M; i++) {
// 		int type,pos,val;cin>>type>>pos>>val;
// 		if (type == 1) {
// 			cout<<updateX(pos,val)<<endl;
// 		} else if (type == 2) {
// 			cout<<updateY(pos,val)<<endl;
// 		}
// 	}
// 	return 0;
// }

Subtask #1

17.0 / 17.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	1 ms	212 KB	Output is correct
5	Correct	1 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	0 ms	312 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 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	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	308 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct

Subtask #2

17.0 / 17.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	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 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	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 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	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	308 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	308 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	308 KB	Output is correct
23	Correct	1 ms	460 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	448 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	448 KB	Output is correct
30	Correct	1 ms	448 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	62456 KB	Output is correct
2	Correct	194 ms	74772 KB	Output is correct
3	Correct	155 ms	66052 KB	Output is correct
4	Correct	173 ms	69840 KB	Output is correct

Subtask #4

23.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	1 ms	212 KB	Output is correct
5	Correct	1 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	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	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	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	448 KB	Output is correct
24	Correct	1 ms	448 KB	Output is correct
25	Correct	1 ms	448 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	448 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	448 KB	Output is correct
33	Correct	64 ms	65336 KB	Output is correct
34	Correct	70 ms	65308 KB	Output is correct
35	Correct	78 ms	72268 KB	Output is correct
36	Correct	76 ms	72212 KB	Output is correct
37	Correct	56 ms	63632 KB	Output is correct
38	Correct	62 ms	64344 KB	Output is correct
39	Correct	45 ms	63360 KB	Output is correct
40	Correct	59 ms	67308 KB	Output is correct
41	Correct	43 ms	63412 KB	Output is correct
42	Correct	46 ms	63456 KB	Output is correct
43	Correct	61 ms	67568 KB	Output is correct
44	Correct	59 ms	67584 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	304 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 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	1 ms	212 KB	Output is correct
9	Correct	1 ms	304 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	304 KB	Output is correct
12	Correct	0 ms	312 KB	Output is correct
13	Correct	0 ms	308 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	304 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	304 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	444 KB	Output is correct
30	Correct	1 ms	448 KB	Output is correct
31	Correct	1 ms	448 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct
33	Correct	101 ms	66100 KB	Output is correct
34	Correct	206 ms	74860 KB	Output is correct
35	Correct	168 ms	66172 KB	Output is correct
36	Correct	203 ms	69980 KB	Output is correct
37	Correct	66 ms	65292 KB	Output is correct
38	Correct	60 ms	65228 KB	Output is correct
39	Correct	81 ms	72324 KB	Output is correct
40	Correct	89 ms	72124 KB	Output is correct
41	Correct	53 ms	63528 KB	Output is correct
42	Correct	60 ms	64388 KB	Output is correct
43	Correct	43 ms	63276 KB	Output is correct
44	Correct	75 ms	67292 KB	Output is correct
45	Correct	56 ms	63496 KB	Output is correct
46	Correct	48 ms	63488 KB	Output is correct
47	Correct	61 ms	67616 KB	Output is correct
48	Correct	60 ms	67704 KB	Output is correct
49	Correct	187 ms	67276 KB	Output is correct
50	Correct	171 ms	67340 KB	Output is correct
51	Correct	131 ms	74168 KB	Output is correct
52	Correct	139 ms	73588 KB	Output is correct
53	Correct	159 ms	65660 KB	Output is correct
54	Correct	103 ms	66128 KB	Output is correct
55	Correct	102 ms	64404 KB	Output is correct
56	Correct	124 ms	69112 KB	Output is correct
57	Correct	95 ms	65024 KB	Output is correct
58	Correct	98 ms	65532 KB	Output is correct
59	Correct	59 ms	67608 KB	Output is correct