| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1065519 |
2024-08-19T08:53:23 Z |
anango |
Horses (IOI15_horses) |
C++17 |
|
332 ms |
56804 KB |
#include "horses.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
int MOD = 1000000007;
int INF = 1LL<<60;
//maintain a set of all indices such that X[i]>1
//consider the last 30 such indices
//then using a max segtree calculate the maximum Y[i] in between these indices, and thus compute the max X[i]*Y[i] at that index
//we can compute the prefix products of the X[i] using another segtree, which allows us to make point updates
//and range product queries
int exp(int base, int exponent) {
int t = base;
int p = 1;
for (int i=0; i<32; i++) {
if (exponent&(1LL<<i)) {
p*=t; p%=MOD;
}
t*=t;
t%=MOD;
}
return p;
}
int inv(int base) {
return exp(base,MOD-2);
}
class productSegTree {
public:
const int sz = 1048576;
vector<int> tree;
productSegTree() {
tree=vector<int>(sz,1);
}
//each node carries the product of its children
void update(int v, int l, int r, int tl, int tr, int assignment) {
if (l>tr || r<tl) return;
if (l<=tl && tr<=r) {
tree[v]=assignment;
tree[v]%=MOD;
return;
}
int m = (tl+tr)/2;
update(2*v,l,r,tl,m,assignment);
update(2*v+1,l,r,m+1,tr,assignment);
tree[v] = tree[2*v]*tree[2*v+1];
tree[v]%=MOD;
}
int query(int v, int l, int r, int tl, int tr) {
if (l>tr || r<tl) return 1;
if (l<=tl && tr<=r) {
return tree[v];
}
int m = (tl+tr)/2;
int a = query(2*v,l,r,tl,m);
int b = query(2*v+1,l,r,m+1,tr);
return (a*b)%MOD;
}
void update_wrapper(int index, int mult) {
update(1,index,index,0,sz/2-1,mult);
}
int query_wrapper(int index) {
//0...index
return query(1,0,index,0,sz/2-1);
}
};
class maxSegTree {
public:
const int sz = 1048576;
vector<int> tree;
maxSegTree() {
tree=vector<int>(sz,0);
}
//each node carries the max of its children
void update(int v, int l, int r, int tl, int tr, int assignment) {
if (l>tr || r<tl) return;
if (l<=tl && tr<=r) {
tree[v]=assignment;
return;
}
int m = (tl+tr)/2;
update(2*v,l,r,tl,m,assignment);
update(2*v+1,l,r,m+1,tr,assignment);
tree[v] = max(tree[2*v],tree[2*v+1]);
}
int query(int v, int l, int r, int tl, int tr) {
if (l>tr || r<tl) return -INF;
if (l<=tl && tr<=r) {
return tree[v];
}
int m = (tl+tr)/2;
int a = query(2*v,l,r,tl,m);
int b = query(2*v+1,l,r,m+1,tr);
return max(a,b);
}
void update_wrapper(int index, int assignment) {
update(1,index,index,0,sz/2-1,assignment);
}
int query_wrapper(int l, int r) {
return query(1,l,r,0,sz/2-1);
}
};
set<int> usefulX;
vector<int> xval,yval;
maxSegTree yseg;
productSegTree xseg;
int n;
int get_answer() {
vector<int> needcheck={0};
auto it = usefulX.end();
for (int i=0; i<32; i++) {
if (it==usefulX.begin()) break;
it--;
int r = *it;
needcheck.push_back(r);
}
needcheck.push_back(n);
sort(needcheck.begin(), needcheck.end());
int answer = -1;
int suffprod = 1;
int bestyval = 0;
int bestsuffprod = 1;
//want maximum value of maxyval / suffprod
int k = needcheck.size();
for (int i=k-2; i>=0; i--) {
if (suffprod>1073741824) break;
int maxyval = yseg.query_wrapper(needcheck[i],needcheck[i+1]-1);
if (maxyval*bestsuffprod>bestyval*suffprod) {
bestsuffprod = suffprod;
bestyval = maxyval;
answer = maxyval*xseg.query_wrapper(needcheck[i]);
answer%=MOD;
}
suffprod*=needcheck[xval[i]];
}
return answer;
}
signed init(signed N, signed X[], signed Y[]) {
n=N;
xval=yval=vector<int>(N,0);
for (int i=0; i<N; i++) {
xval[i] = X[i]; yval[i] = Y[i];
if (xval[i]!=1) usefulX.insert(i);
}
for (int i=0; i<N; i++) {
xseg.update_wrapper(i,X[i]);
yseg.update_wrapper(i,Y[i]);
}
return get_answer();
}
signed updateX(signed pos, signed val) {
xval[pos] = val;
xseg.update_wrapper(pos,val);
return get_answer();
}
signed updateY(signed pos, signed val) {
yval[pos] = val;
yseg.update_wrapper(pos,val);
return get_answer();
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:160:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
160 | return get_answer();
| ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:166:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
166 | return get_answer();
| ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:172:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
172 | return get_answer();
| ~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16732 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
16732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16728 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
332 ms |
56804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
16732 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16732 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
