oj.uz

Submission #310499

# Submission time Handle Problem Language Result Execution time Memory
310499 2020-10-07T07:14:36 Z amunduzbaev Horses (IOI15_horses) C++14
100 / 100
 443 ms 79608 KB 
#include "horses.h"
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int n;
const int NN = 1e6+5;
const ll mod = 1e9+7;
ll a[NN];
ll b[NN];

ll binpow(ll p, ll q){
	if(q == 0)return 1ll;
	ll temp = binpow(p, q/2);
	temp *= temp;
	temp %= mod;
	if(q%2==1)temp *= p;
	return temp%mod;
}

struct Node {
	ld sum;
	ll answ;
};
Node neutral = {0., 1ll};
int sz;
vector<Node> t;
vector<Node> ans;
Node combine(Node f, Node s){
	return {f.sum+s.sum, (f.answ*s.answ)%mod};
}
Node mx(Node f, Node s){
	if(f.sum > s.sum)return f;
	else return s;
}
void build(){
	sz=1;
	while(sz<n)sz<<=1;
	t.assign(sz*2, neutral);
	ans.assign(sz*2, neutral);
	for(int i=0;i<n;i++){
		t[i+sz].sum = log2(a[i]);
		t[i+sz].answ = a[i];
	}for(int i=1;i<sz;i++){
		t[i+sz].sum += t[i+sz-1].sum;
		t[i+sz].answ *= t[i+sz-1].answ;t[i+sz].answ%=mod;
	}for(int i=0;i<sz;i++){
		ans[i+sz].sum = t[i+sz].sum+log2(b[i]);
		ans[i+sz].answ =(t[i+sz].answ*b[i])%mod;
	}for(int i=sz-1;i>0;i--){
		ans[i] = mx(ans[i*2], ans[i*2+1]);
	}
}
Node getpref(int i){
	ld ansd = 0.;
	ll ansl = 1;
	for(i+=sz; i>0; i>>=1){
		ansd += t[i].sum;
		ansl *= t[i].answ;ansl%=mod;
	}return {ansd, ansl};
}
void push(int l, int r, int node){
	if(r-l == 1)return;
	t[node*2] = combine(t[node], t[node*2]);
	t[node*2+1]=combine(t[node], t[node*2+1]);
	ans[node*2] = combine(ans[node*2], t[node]);
	ans[node*2+1]=combine(ans[node*2+1], t[node]);

	t[node] = neutral;
	ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyX(int l, int r, int lx, int rx, Node val, int node){
	if(lx >= r || rx <= l)return;
	push(lx, rx, node);
	if(lx >= l && rx <= r){
		t[node] = combine(t[node], val);
		ans[node]=combine(ans[node], val);
		return;
	}int mid = (lx+rx)/2;
	modifyX(l, r, lx, mid, val, node*2);
	modifyX(l, r, mid, rx, val, node*2+1);
	ans[node] = mx(ans[node*2], ans[node*2+1]);
}
void modifyY(int pos, int lx, int rx, Node val, int node){
	if(rx-lx == 1){
		ans[node] = val;
		return;
	}int mid = (lx+rx)/2;
	push(lx, rx, node);
	if(mid <= pos){
		modifyY(pos, mid, rx, val, node*2+1);
	}else {
		modifyY(pos, lx, mid, val, node*2);
	}ans[node] = mx(ans[node*2], ans[node*2+1]);
}//===============================================


int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=0;i<n;i++)a[i] = X[i];
	for(int i=0;i<n;i++)b[i] = Y[i];
	build();
	return ans[1].answ;
}

int updateX(int pos, int val) {
	modifyX(pos, sz, 0, sz, {log2(val)-log2(a[pos]), ((val*binpow(a[pos],mod-2))%mod)}, 1);
	a[pos] = val;
	return ans[1].answ;
}

int updateY(int pos, int val) {
	Node X = getpref(pos);
	modifyY(pos, 0, sz, {X.sum+log2(val), (X.answ*val)%mod}, 1);
	b[pos] = val;
	return ans[1].answ;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:104:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |  return ans[1].answ;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  110 |  return ans[1].answ;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:117:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |  return ans[1].answ;

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 2 ms 512 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 1 ms 512 KB Output is correct
32 Correct 2 ms 512 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 78712 KB Output is correct
2 Correct 440 ms 79480 KB Output is correct
3 Correct 374 ms 79308 KB Output is correct
4 Correct 443 ms 79224 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 416 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 2 ms 512 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 1 ms 512 KB Output is correct
32 Correct 2 ms 512 KB Output is correct
33 Correct 128 ms 78328 KB Output is correct
34 Correct 128 ms 78328 KB Output is correct
35 Correct 146 ms 78584 KB Output is correct
36 Correct 146 ms 78584 KB Output is correct
37 Correct 103 ms 78328 KB Output is correct
38 Correct 115 ms 78328 KB Output is correct
39 Correct 87 ms 78328 KB Output is correct
40 Correct 117 ms 78328 KB Output is correct
41 Correct 86 ms 78456 KB Output is correct
42 Correct 88 ms 78328 KB Output is correct
43 Correct 100 ms 78256 KB Output is correct
44 Correct 100 ms 78200 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 2 ms 640 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 2 ms 512 KB Output is correct
30 Correct 2 ms 512 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 2 ms 512 KB Output is correct
33 Correct 209 ms 79608 KB Output is correct
34 Correct 425 ms 79480 KB Output is correct
35 Correct 369 ms 79224 KB Output is correct
36 Correct 443 ms 79352 KB Output is correct
37 Correct 128 ms 78328 KB Output is correct
38 Correct 128 ms 78328 KB Output is correct
39 Correct 147 ms 78712 KB Output is correct
40 Correct 147 ms 78616 KB Output is correct
41 Correct 104 ms 78328 KB Output is correct
42 Correct 119 ms 78328 KB Output is correct
43 Correct 88 ms 78328 KB Output is correct
44 Correct 118 ms 78328 KB Output is correct
45 Correct 89 ms 78328 KB Output is correct
46 Correct 89 ms 78328 KB Output is correct
47 Correct 103 ms 78200 KB Output is correct
48 Correct 101 ms 78200 KB Output is correct
49 Correct 404 ms 79224 KB Output is correct
50 Correct 405 ms 79224 KB Output is correct
51 Correct 292 ms 79608 KB Output is correct
52 Correct 301 ms 79608 KB Output is correct
53 Correct 384 ms 79352 KB Output is correct
54 Correct 299 ms 79096 KB Output is correct
55 Correct 216 ms 78456 KB Output is correct
56 Correct 307 ms 79352 KB Output is correct
57 Correct 201 ms 79224 KB Output is correct
58 Correct 235 ms 79480 KB Output is correct
59 Correct 105 ms 78200 KB Output is correct