oj.uz

답안 #574106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574106 2022-06-07T19:35:29 Z perchuts 말 (IOI15_horses) C++17
17 / 100
 77 ms 57860 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, 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.tot*r.tot)%mod;
	if(y[l.idx]>l.suf*r.best)res.best = l.best, res.suf = min(inf, l.suf*r.tot), res.idx = l.idx;
	else res.best = (l.totmod*r.best)%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 = (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 = (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;
	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 seg[1].best;
}

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

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


// 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;
// }

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |  return seg[1].best;
      |         ~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 308 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 1 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 0 ms 212 KB Output is correct

Subtask #2
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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 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 0 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 300 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 57860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 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 308 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 308 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 304 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 0 ms 212 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Incorrect 1 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 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 304 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 1 ms 304 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 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 1 ms 212 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 212 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 Incorrect 1 ms 212 KB Output isn't correct
23 Halted 0 ms 0 KB -