oj.uz

Submission #154841

# Submission time Handle Problem Language Result Execution time Memory
154841 2019-09-25T08:21:35 Z junodeveloper Horses (IOI15_horses) C++14
100 / 100
 569 ms 49436 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int off=1<<19;
const int mod=1e9+7;
 
struct MULT {
	int tree[off<<1];
	MULT() {memset(tree,0,sizeof(tree));}
	void update(int p,int x) {
		p+=off;
		tree[p]=x;p/=2;
		while(p>0) {
			tree[p]=(ll)tree[p<<1]*tree[p<<1|1]%mod;
			p>>=1;
		}
	}
	int query(int l,int r) {
		int ret=1;
		l+=off,r+=off;
		while(l<r) {
			if(l%2==1) ret=(ll)ret*tree[l++]%mod;
			if(r%2==0) ret=(ll)ret*tree[r--]%mod;
			l>>=1,r>>=1;
		}
		if(l==r) ret=(ll)ret*tree[l]%mod;
		return ret;
	}
} mult;
 
struct MAXT {
	int tree[off<<1];
	MAXT() {memset(tree,0,sizeof(tree));}
	void update(int p,int x) {
		p+=off;
		tree[p]=x;p/=2;
		while(p>0) {
			tree[p]=max(tree[p<<1],tree[p<<1|1]);
			p>>=1;
		}
	}
	int query(int l,int r) {
		int ret=0;
		l+=off,r+=off;
		while(l<r) {
			if(l%2==1) ret=max(ret,tree[l++]);
			if(r%2==0) ret=max(ret,tree[r--]);
			l>>=1,r>>=1;
		}
		if(l==r) ret=max(ret,tree[l]);
		return ret;
	}
} maxt;
 
int n;
int *x, *y;
set<int> st;
 
int solve() {
	auto it=st.end(); it--;
	int i,j; ll r=1;
	while(it!=st.begin()) {
		r*=x[*it];
		if(r>(ll)1e9) break;
		it--;
	}
	int fir=*it;
	r=1; ll mx=0;
	while(it!=st.end()) {
		i=*it;
		if(next(it)==st.end()) j=n-1;
		else j=*next(it)-1;
		mx=max(mx,(ll)r*maxt.query(i,j));it++;
		if(it!=st.end()) r*=x[*it];
	}
	mx%=mod;
	return (ll)mult.query(0,fir)*mx%mod;
}
 
int init(int N, int X[], int Y[]) {
	n=N;
	x=X,y=Y;
	int i;
	for(i=0;i<n;i++) {
		mult.update(i,x[i]);
		maxt.update(i,y[i]);
		if(x[i]!=1) st.insert(i);
	}
	st.insert(0);
	return solve();
}
 
int updateX(int pos, int val) {
	if(pos&&x[pos]!=1) {
		st.erase(pos);
	}
	x[pos]=val;
	if(pos&&x[pos]!=1) {
		st.insert(pos);
	}
	mult.update(pos,val);
	return solve();
}
 
int updateY(int pos, int val) {
	y[pos]=val;
	maxt.update(pos,val);
	return solve();
}

Compilation message

horses.cpp: In member function 'void MULT::update(int, int)':
horses.cpp:17:39: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    tree[p]=(ll)tree[p<<1]*tree[p<<1|1]%mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int MULT::query(int, int)':
horses.cpp:25:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    if(l%2==1) ret=(ll)ret*tree[l++]%mod;
                   ~~~~~~~~~~~~~~~~~^~~~
horses.cpp:26:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    if(r%2==0) ret=(ll)ret*tree[r--]%mod;
                   ~~~~~~~~~~~~~~~~~^~~~
horses.cpp:29:31: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if(l==r) ret=(ll)ret*tree[l]%mod;
                ~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int solve()':
horses.cpp:80:33: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return (ll)mult.query(0,fir)*mx%mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 40760 KB Output is correct
2 Correct 545 ms 49276 KB Output is correct
3 Correct 471 ms 40688 KB Output is correct
4 Correct 537 ms 44664 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 9 ms 8568 KB Output is correct
4 Correct 9 ms 8568 KB Output is correct
5 Correct 9 ms 8568 KB Output is correct
6 Correct 11 ms 8568 KB Output is correct
7 Correct 9 ms 8568 KB Output is correct
8 Correct 9 ms 8568 KB Output is correct
9 Correct 11 ms 8568 KB Output is correct
10 Correct 11 ms 8568 KB Output is correct
11 Correct 9 ms 8568 KB Output is correct
12 Correct 10 ms 8568 KB Output is correct
13 Correct 9 ms 8568 KB Output is correct
14 Correct 9 ms 8568 KB Output is correct
15 Correct 10 ms 8568 KB Output is correct
16 Correct 9 ms 8568 KB Output is correct
17 Correct 10 ms 8568 KB Output is correct
18 Correct 9 ms 8568 KB Output is correct
19 Correct 9 ms 8568 KB Output is correct
20 Correct 9 ms 8600 KB Output is correct
21 Correct 10 ms 8568 KB Output is correct
22 Correct 9 ms 8568 KB Output is correct
23 Correct 10 ms 8568 KB Output is correct
24 Correct 12 ms 8568 KB Output is correct
25 Correct 10 ms 8568 KB Output is correct
26 Correct 10 ms 8568 KB Output is correct
27 Correct 10 ms 8696 KB Output is correct
28 Correct 10 ms 8568 KB Output is correct
29 Correct 10 ms 8568 KB Output is correct
30 Correct 12 ms 8568 KB Output is correct
31 Correct 11 ms 8568 KB Output is correct
32 Correct 12 ms 8568 KB Output is correct
33 Correct 139 ms 16632 KB Output is correct
34 Correct 130 ms 16548 KB Output is correct
35 Correct 348 ms 46852 KB Output is correct
36 Correct 343 ms 46904 KB Output is correct
37 Correct 128 ms 14724 KB Output is correct
38 Correct 216 ms 27640 KB Output is correct
39 Correct 121 ms 14676 KB Output is correct
40 Correct 343 ms 41884 KB Output is correct
41 Correct 122 ms 14584 KB Output is correct
42 Correct 124 ms 14584 KB Output is correct
43 Correct 318 ms 42360 KB Output is correct
44 Correct 321 ms 42416 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Correct 9 ms 8572 KB Output is correct
3 Correct 9 ms 8568 KB Output is correct
4 Correct 9 ms 8568 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 10 ms 8568 KB Output is correct
7 Correct 9 ms 8540 KB Output is correct
8 Correct 9 ms 8568 KB Output is correct
9 Correct 9 ms 8568 KB Output is correct
10 Correct 10 ms 8568 KB Output is correct
11 Correct 9 ms 8568 KB Output is correct
12 Correct 9 ms 8568 KB Output is correct
13 Correct 9 ms 8568 KB Output is correct
14 Correct 9 ms 8572 KB Output is correct
15 Correct 9 ms 8568 KB Output is correct
16 Correct 9 ms 8568 KB Output is correct
17 Correct 10 ms 8568 KB Output is correct
18 Correct 9 ms 8568 KB Output is correct
19 Correct 10 ms 8568 KB Output is correct
20 Correct 9 ms 8568 KB Output is correct
21 Correct 9 ms 8568 KB Output is correct
22 Correct 9 ms 8444 KB Output is correct
23 Correct 11 ms 8568 KB Output is correct
24 Correct 10 ms 8568 KB Output is correct
25 Correct 10 ms 8568 KB Output is correct
26 Correct 10 ms 8568 KB Output is correct
27 Correct 10 ms 8568 KB Output is correct
28 Correct 10 ms 8568 KB Output is correct
29 Correct 10 ms 8568 KB Output is correct
30 Correct 10 ms 8572 KB Output is correct
31 Correct 12 ms 8568 KB Output is correct
32 Correct 11 ms 8568 KB Output is correct
33 Correct 393 ms 40896 KB Output is correct
34 Correct 482 ms 49436 KB Output is correct
35 Correct 454 ms 40764 KB Output is correct
36 Correct 569 ms 44552 KB Output is correct
37 Correct 138 ms 16632 KB Output is correct
38 Correct 137 ms 16580 KB Output is correct
39 Correct 346 ms 46908 KB Output is correct
40 Correct 347 ms 46996 KB Output is correct
41 Correct 129 ms 14712 KB Output is correct
42 Correct 214 ms 27544 KB Output is correct
43 Correct 121 ms 14560 KB Output is correct
44 Correct 327 ms 42020 KB Output is correct
45 Correct 122 ms 14584 KB Output is correct
46 Correct 126 ms 14572 KB Output is correct
47 Correct 319 ms 42308 KB Output is correct
48 Correct 324 ms 42444 KB Output is correct
49 Correct 196 ms 19656 KB Output is correct
50 Correct 190 ms 19684 KB Output is correct
51 Correct 418 ms 48888 KB Output is correct
52 Correct 408 ms 48308 KB Output is correct
53 Correct 248 ms 17876 KB Output is correct
54 Correct 296 ms 31496 KB Output is correct
55 Correct 164 ms 15608 KB Output is correct
56 Correct 393 ms 43820 KB Output is correct
57 Correct 165 ms 16228 KB Output is correct
58 Correct 189 ms 16760 KB Output is correct
59 Correct 320 ms 42320 KB Output is correct