| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 574107 |
2022-06-07T19:41:31 Z |
perchuts |
Horses (IOI15_horses) |
C++17 |
|
107 ms |
62216 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 = 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 = (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].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;
// }
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
81 | return seg[1].bestmod;
| ~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
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 |
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 |
1 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 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 |
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 |
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 |
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 |
| 21 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
62216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
1 ms |
212 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 |
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 |
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 |
| 21 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 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 |
0 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 |
1 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 |
1 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 |
| 21 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
