| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 795461 |
2023-07-27T10:05:18 Z |
Cauchico |
Horses (IOI15_horses) |
C++14 |
|
925 ms |
67820 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long long int;
int n;
set<pair<int,int>> s;
vector<ll> x,y,tx,ty;
ll MOD = 1e9 + 7;
void Xupdate(int v, int tl, int tr, ll pos, ll val) {
if (tl > pos or tr < pos) return;
if (tl == tr) tx[v] = val;
else {
int tm = (tr+tl)/2;
Xupdate(2*v,tl,tm,pos,val);
Xupdate(2*v+1,tm+1,tr,pos,val);
tx[v] = (tx[2*v]*tx[2*v+1])%MOD;
}
}
void Yupdate(int v, int tl, int tr, ll pos, ll val) {
if (tl > pos or tr < pos) return;
if (tl == tr) ty[v] = val;
else {
int tm = (tr+tl)/2;
Yupdate(2*v,tl,tm,pos,val);
Yupdate(2*v+1,tm+1,tr,pos,val);
ty[v] = max(ty[2*v],ty[2*v+1]);
}
}
ll Xquery(int v, int tl, int tr, ll l, ll r) {
if (tl > r or tr < l) return 1LL;
else if (tl >= l and tr <= r) return tx[v];
else {
int tm = (tr+tl)/2;
return (Xquery(2*v,tl,tm,l,r)*Xquery(2*v+1,tm+1,tr,l,r))%MOD;
}
}
ll Yquery(int v, int tl, int tr, ll l, ll r) {
if (tl > r or tr < l) return 0LL;
else if (tl >= l and tr <= r) return ty[v];
else {
int tm = (tr+tl)/2;
return max(Yquery(2*v,tl,tm,l,r), Yquery(2*v+1,tm+1,tr,l,r));
}
}
int update() {
auto can = s.end();
for (int i=0;i<=32 and can != s.begin();i++) can--;
bool in1 = !(can->first);
while (can != s.end() and !can->first) can++;
if (can == s.end()) return Yquery(1,0,n-1,0,n-1);
ll ans = can->second-1, mxy=(in1 ? Yquery(1,0,n-1,0,ans-1) : y[ans]);
ll px = 1;
//cout << Yquery(1,0,n-1,0,2) << " hmm \n";
while (can != s.end()) {
int i = can->second;
//cout << i << " " << px << " " << Yquery(1,0,n-1,3,3) << "\n";
auto nxt = can; nxt++;
int nx;
if (nxt == s.end()) {
nx = n-1;
} else {
nx = nxt->second-1;
}
ll xi = x[i], yi = Yquery(1,0,n-1,i,nx);
//cout << "i, nx, mxy " << i << " " << nx << " " << yi << "\n";
if (px*xi > MOD or mxy < px*xi*yi) {
ans = i; px = 1; mxy = yi;
} else {
px *= xi;
}
can++;
}
//cout << ans << " " << s.size() << " ";
return (int) ((1LL*mxy*Xquery(1,0,n-1,0,ans))%MOD);
}
int init(int N, int X[], int Y[]) {
//return 42;
n = N; x.resize(n); y.resize(n);
tx.resize(4*n,1); ty.resize(4*n,0);
for (int i=0;i<n;i++) {
x[i] = X[i]; y[i] = Y[i];
s.insert({x[i]>1,i});
Xupdate(1,0,n-1,i,x[i]);
Yupdate(1,0,n-1,i,y[i]);
}
//cout << Xquery(1,0,n-1,0,1) <<" ";
return update();
}
int updateX(int pos, int val) {
//return 43;
s.erase({x[pos]>1,pos});
s.insert({val>1,pos});
x[pos] = val;
Xupdate(1,0,n-1,pos,val);
return update();
}
int updateY(int pos, int val) {
//return 44;
y[pos] = val;
Yupdate(1,0,n-1,pos,val);
return update();
}
/*signed main() {
freopen("horses.in", "r+",stdin);
freopen("horses.out", "w+",stdout);
int n_; cin >> n_;
int X[n_], Y[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) << "\n";
int m; cin >> m;
while (m--) {
int a,b,c; cin >> a >> b >> c;
if (a==1) {
cout << updateX(b,c) << "\n";
} else {
cout << updateY(b,c) << "\n";
}
}
}*/
Compilation message
horses.cpp: In function 'int update()':
horses.cpp:54:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
54 | if (can == s.end()) return Yquery(1,0,n-1,0,n-1);
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
788 ms |
67808 KB |
Output is correct |
| 2 |
Correct |
925 ms |
67820 KB |
Output is correct |
| 3 |
Correct |
847 ms |
67748 KB |
Output is correct |
| 4 |
Correct |
923 ms |
67812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
