oj.uz

Submission #730122

# Submission time Handle Problem Language Result Execution time Memory
730122 2023-04-25T09:55:43 Z sentheta Horses (IOI15_horses) C++17
37 / 100
 514 ms 40540 KB 
#include "horses.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const Int MOD = 1e9+7;
const int N = 5e5+5;

int n;
int *x, *y;

#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Maxsegtree{
	int mx[2*N];
	void upd(int i,int val,int v=0,int tl=0,int tr=n-1){
		if(tl==tr){
			mx[v] = val; return;
		}
		if(i<=mid) upd(i,val, lc,tl,mid);
		else upd(i,val, rc,mid+1,tr);
		mx[v] = max(mx[lc], mx[rc]);
	}
	int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return 0;
		if(l<=tl && tr<=r) return mx[v];
		return max(qry(l,r, lc,tl,mid), qry(l,r, rc,mid+1,tr));
	}
} maxtree;
struct Mulsegtree{
	Int prod[2*N];
	void upd(int i,Int val,int v=0,int tl=0,int tr=n-1){
		if(tl==tr){
			prod[v] = val; return;
		}
		if(i<=mid) upd(i,val, lc,tl,mid);
		else upd(i,val, rc,mid+1,tr);
		prod[v] = prod[lc] * prod[rc] % MOD;
	}
	Int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return 1;
		if(l<=tl && tr<=r) return prod[v];
		return qry(l,r, lc,tl,mid) * qry(l,r, rc,mid+1,tr) % MOD;
	}
} multree;
#undef mid

set<int> sx;

int solve(){
	if(sx.empty()){
		return (int)maxtree.qry(0,n-1);
	}

	int r = n-1;
	// Int ratio = 1;
	Int ans = 0, ansmod = 0;
	for(auto it=sx.end(); it!=sx.begin(); ){
		it = prev(it);
		int l = *it;

		Int mxy = maxtree.qry(l,r);
		// dbg(mxy);
		if(mxy > (Int)ans){
			ans = mxy;
			ansmod = multree.qry(0,l) *mxy%MOD;
		}

		if(1.*x[l]*ans > MOD) break;
		ans *= x[l];
		// ratio *= x[l];
		// if(ratio > MOD) break;
		r = l-1;
	}

	return (int)ansmod;
}

int init(int _n,int _x[], int _y[]){
	n = _n; x = _x; y = _y;

	rep(i,0,n){
		maxtree.upd(i,y[i]);

		multree.upd(i,x[i]);
		if(x[i]!=1) sx.insert(i);
	}

	// dbg(n);
	return solve();
}

int updateX(int i,int val){
	// assert(0);

	if(x[i]!=1) sx.erase(i);
	x[i] = val;
	multree.upd(i,x[i]);
	if(x[i]!=1) sx.insert(i);

	// dbg(n);
	return solve();
}

int updateY(int i,int val){
	// assert(0);

	y[i] = val;
	maxtree.upd(i,y[i]);

	// dbg(n);
	return solve();
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:101:14: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  101 |   if(1.*x[l]*ans > MOD) break;
      |              ^~~

Subtask #1
17.0 / 17.0

# 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 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 0 ms 212 KB Output is correct
9 Correct 1 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 1 ms 340 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 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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 1 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 1 ms 212 KB Output is correct
12 Correct 1 ms 212 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 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 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 2 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 40492 KB Output is correct
2 Correct 397 ms 40540 KB Output is correct
3 Correct 379 ms 40384 KB Output is correct
4 Correct 432 ms 40440 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory 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 1 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 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 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 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 3 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 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 1 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 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 1 ms 304 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 3 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -