# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
533221 |
2022-03-05T06:56:04 Z |
ivan24 |
Horses (IOI15_horses) |
C++14 |
|
981 ms |
88200 KB |
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
const ll INF = 1e18+10;
const ll MOD = 1e9+7;
const ll MX_VAL = 1e9;
struct stnode {
ll prod,mx;
stnode (){ prod = 1; mx = 0; }
stnode merge_node (const stnode& rhs){
stnode res;
res.prod = prod*rhs.prod; res.prod %= MOD;
res.mx = max(mx,rhs.mx);
return res;
}
};
ll modpow (ll b, ll e){
ll res = 1;
while (e > 0){
if (e%2) res *= b;
e /= 2; b *= b;
res %= MOD; b %= MOD;
}
return res;
}
struct frac {
ll n,d;
frac(){ n = 1; d = 1;}
frac (ll _n, ll _d){
n = _n; d = _d;
}
bool operator>(const frac& rhs) const{
return n*rhs.d > rhs.n*d;
}
bool operator<(const frac& rhs) const{
return n*rhs.d < rhs.n*d;
}
ll mult (ll x){
x *= n; x %= MOD;
x *= modpow(d,MOD-2); x %= MOD;
return x;
}
};
class SegTree {
private:
vector<stnode> st;
ll n;
vi a,b;
ll left(ll x){ return (x << 1); }
ll right(ll x){ return ((x << 1) + 1); }
void build (ll i, ll l, ll r){
if (l == r){
st[i].prod = a[i];
st[i].mx = b[i];
}else{
ll m = (l+r)/2;
build(left(i),l,m);
build(right(i),m+1,r);
st[i] = st[left(i)].merge_node(st[right(i)]);
}
}
stnode query (ll i, ll l, ll r, ll ql, ll qr){
if (qr >= r && l >= ql){
return st[i];
}else if (l > qr || ql > r){
return stnode();
}else{
ll m = (l+r)/2;
stnode lres = query(left(i),l,m,ql,qr);
stnode rres = query(right(i),m+1,r,ql,qr);
return lres.merge_node(rres);
}
}
void update (ll i, ll l, ll r, ll type, ll val, ll idx){
//cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
if (r >= idx && idx >= l){
//cout << i << " " << l << " " << r << " " << type << " " << val << " " << idx << endl;
if (r == l){
if (type == 0) st[i].prod = val;
else st[i].mx = val;
}else{
ll m = (l+r)/2;
update(left(i),l,m,type,val,idx);
update(right(i),m+1,r,type,val,idx);
st[i] = st[left(i)].merge_node(st[right(i)]);
}
}
}
public:
SegTree (vi _a, vi _b): a(_a), b(_b){
n = a.size();
st.resize(4*n);
build(1,0,n-1);
}
SegTree(ll _n){
n = _n;
a.assign(n,1);
b.assign(n,0);
st.assign(4*n,stnode());
}
SegTree(){}
ll query (ll type, ll l, ll r){
stnode res;
//cout << "queried: " << type << " " << l << " " << r << endl;
if (r >= l) res = query(1,0,n-1,l,r);
if (type == 0) return res.prod;
else return res.mx;
}
void update (ll type, ll val, ll idx){
//cout << "update: " << type << " " << val << " " << idx << endl;
//cout << n << endl;
update (1,0,n-1,type,val,idx);
}
};
class WeirdDS {
private:
SegTree st;
vi x,y;
set<ll> overone;
ll n;
public:
WeirdDS(int _n){
n = _n;
st = SegTree(n);
x.assign(n,1);
y.assign(n,0);
set<ll>().swap(overone);
overone.insert(0);
}
WeirdDS(){}
void updateX(ll pos, ll val){
st.update(0,val,pos);
if (val == 1){
auto itr = overone.find(-pos);
if (itr != overone.end())
overone.erase(itr);
}else{
overone.insert(-pos);
}
overone.insert(0);
x[pos] = val;
}
void updateY(ll pos, ll val){
st.update(1,val,pos);
}
ll query (){
bool broke = false;
ll prv = n;
ll ctr = 1;
frac maxMult;
for (auto i: overone){
ll bigY = st.query(1,-i,prv-1);
frac curMult = frac(bigY,ctr);
if (curMult > maxMult) maxMult = curMult;
prv = -i;
ctr *= x[-i];
if (x[-i] == 1 && i != 0) return INF;
if (ctr > MX_VAL) break;
}
return maxMult.mult(st.query(0,0,n-1));
}
};
WeirdDS myDS;
int init(int n, int x[], int y[]) {
//cout.setstate(ios_base::failbit);
myDS = WeirdDS(n);
for (ll i = 0; n > i; i++){
myDS.updateX(i,x[i]);
myDS.updateY(i,y[i]);
}
////cout << myDS.query() << endl;
return myDS.query();
}
int updateX(int pos, int val) {
//cout << "updateX: " << pos << " " << val << endl;
myDS.updateX(pos,val);
//cout << res << endl;
return myDS.query();
}
int updateY(int pos, int val) {
//cout << "updateY: " << pos << " " << val << endl;
myDS.updateY(pos,val);
//cout << res << endl;
return myDS.query();
}
Compilation message
horses.cpp: In member function 'll WeirdDS::query()':
horses.cpp:170:14: warning: unused variable 'broke' [-Wunused-variable]
170 | bool broke = false;
| ^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:197:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
197 | return myDS.query();
| ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:204:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
204 | return myDS.query();
| ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:211:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
211 | return myDS.query();
| ~~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
308 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
4 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
332 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
951 ms |
77416 KB |
Output is correct |
2 |
Correct |
611 ms |
88200 KB |
Output is correct |
3 |
Correct |
602 ms |
79320 KB |
Output is correct |
4 |
Correct |
665 ms |
83268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
2 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
460 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
4 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
332 KB |
Output is correct |
29 |
Correct |
2 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
3 ms |
332 KB |
Output is correct |
33 |
Correct |
267 ms |
51308 KB |
Output is correct |
34 |
Correct |
262 ms |
51304 KB |
Output is correct |
35 |
Correct |
485 ms |
74684 KB |
Output is correct |
36 |
Correct |
441 ms |
74688 KB |
Output is correct |
37 |
Correct |
299 ms |
51308 KB |
Output is correct |
38 |
Correct |
369 ms |
63296 KB |
Output is correct |
39 |
Correct |
267 ms |
53148 KB |
Output is correct |
40 |
Correct |
436 ms |
80700 KB |
Output is correct |
41 |
Correct |
290 ms |
53224 KB |
Output is correct |
42 |
Correct |
292 ms |
53276 KB |
Output is correct |
43 |
Correct |
430 ms |
81016 KB |
Output is correct |
44 |
Correct |
431 ms |
81032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
332 KB |
Output is correct |
25 |
Correct |
2 ms |
332 KB |
Output is correct |
26 |
Correct |
2 ms |
332 KB |
Output is correct |
27 |
Correct |
6 ms |
332 KB |
Output is correct |
28 |
Correct |
2 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
4 ms |
332 KB |
Output is correct |
33 |
Correct |
981 ms |
77552 KB |
Output is correct |
34 |
Correct |
617 ms |
88168 KB |
Output is correct |
35 |
Correct |
636 ms |
79436 KB |
Output is correct |
36 |
Correct |
685 ms |
83400 KB |
Output is correct |
37 |
Correct |
255 ms |
55244 KB |
Output is correct |
38 |
Correct |
254 ms |
55236 KB |
Output is correct |
39 |
Correct |
420 ms |
85548 KB |
Output is correct |
40 |
Correct |
447 ms |
85532 KB |
Output is correct |
41 |
Correct |
319 ms |
53448 KB |
Output is correct |
42 |
Correct |
369 ms |
66324 KB |
Output is correct |
43 |
Correct |
244 ms |
53240 KB |
Output is correct |
44 |
Correct |
424 ms |
80592 KB |
Output is correct |
45 |
Correct |
273 ms |
53368 KB |
Output is correct |
46 |
Correct |
281 ms |
53324 KB |
Output is correct |
47 |
Correct |
390 ms |
81196 KB |
Output is correct |
48 |
Correct |
401 ms |
80928 KB |
Output is correct |
49 |
Correct |
385 ms |
58288 KB |
Output is correct |
50 |
Correct |
374 ms |
58212 KB |
Output is correct |
51 |
Correct |
588 ms |
87528 KB |
Output is correct |
52 |
Correct |
523 ms |
87028 KB |
Output is correct |
53 |
Correct |
905 ms |
56548 KB |
Output is correct |
54 |
Correct |
561 ms |
70080 KB |
Output is correct |
55 |
Correct |
347 ms |
54216 KB |
Output is correct |
56 |
Correct |
508 ms |
82396 KB |
Output is correct |
57 |
Correct |
663 ms |
54956 KB |
Output is correct |
58 |
Correct |
785 ms |
55372 KB |
Output is correct |
59 |
Correct |
444 ms |
80932 KB |
Output is correct |