oj.uz

Submission #574108

# Submission time Handle Problem Language Result Execution time Memory
574108 2022-06-07T19:49:50 Z perchuts Horses (IOI15_horses) C++17
100 / 100
 206 ms 74860 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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