oj.uz

Submission #65771

# Submission time Handle Problem Language Result Execution time Memory
65771 2018-08-08T17:53:07 Z Hoget157 Horses (IOI15_horses) C++14
100 / 100
 509 ms 52836 KB 
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;

ll n;

class RMQ{
	ll seg,ini;
	vector<ll> dat;
	function<ll(ll,ll)> f;
	public:
	RMQ() : seg(1){}
	void init(ll def,function<ll(ll,ll)> F){
		ini = def;
		f = F;
		while(seg < n) seg *= 2;
		dat.resize(seg * 2 - 1);
		for(ll i = 0;i < seg * 2 - 1;i++) dat[i] = ini;
	}
	void update(ll i,ll x){
		i += seg - 1;
		dat[i] = x;
		while(i){
			i = (i - 1) / 2;
			dat[i] = f(dat[i * 2 + 1],dat[i * 2 + 2]);
		}
	}
	ll get(ll a){
		return dat[a + seg - 1];
	}
	ll get(ll a,ll b){
		ll ans = ini,pos = seg;
		while(a != b){
			if(a % 2) ans = f(ans,dat[pos - 1 + a++]);
			if(b % 2) ans = f(ans,dat[pos - 1 + --b]);
			pos /= 2;
			a /= 2;
			b /= 2;
		}
		return ans;
	}
	ll find(ll a,ll b,bool isl){
		ll pos = seg,ans = 1000000000;
		if(b == -1) b = seg;
		while(a != b){
			if(a % 2 && dat[pos - 1 + a++] != 1) break;
			if(b % 2 && dat[pos - 1 + --b] != 1) break;
			pos /= 2;
			a /= 2;
			b /= 2;
		}
		if(isl){
			pos += a - 2;
			while(pos < seg - 1){
				if(dat[pos * 2 + 1] != 1) pos = pos * 2 + 1;
				else pos = pos * 2 + 2;
			}
		}else{
			pos += b - 1;
			while(pos < seg - 1){
				if(dat[pos * 2 + 2] != 1) pos = pos * 2 + 2;
				else pos = pos * 2 + 1;
			}
		}
		return pos - seg + 1;
	}
};

RMQ rmq1,rmq2,seki;

ll calc(){
	ll pos = n - 1,tmp = 1,ma = 0,ans;
	while(pos > 0){
		pos = rmq1.find(0,pos,false);
		ll t = rmq1.get(pos);
		if(tmp * t > 1000000000ll) break;
		tmp *= t;
	}
	ans = seki.get(0,pos + 1);
	tmp = 1;
	while(pos < n - 1){
		ll nxt = rmq1.find(pos + 1,-1,true);
		ma = max(ma,tmp * rmq2.get(pos,nxt));
		tmp *= rmq1.get(nxt);
		pos = nxt;
	}
	return ma % MOD * ans % MOD;
}

ll init(int N,int x[],int y[]){
	n = N + 2;
	rmq1.init(0,[](ll a,ll b){ return max(a,b); });
	rmq2.init(0,[](ll a,ll b){ return max(a,b); });
	seki.init(1,[](ll a,ll b){ return a * b % MOD; });
	rmq1.update(0,MOD);
	rmq1.update(n - 1,MOD);
	for(ll i = 0;i < n - 2;i++){
		rmq1.update(i + 1,x[i]);
		rmq2.update(i + 1,y[i]);
		seki.update(i + 1,x[i]);
	}
	return calc();
}

ll updateX(int pos,int val){
	rmq1.update(pos + 1,val);
	seki.update(pos + 1,val);
	return calc();
}

ll updateY(int pos,int val){
	rmq2.update(pos + 1,val);
	return calc();
}

/*signed main(){
	int N,m,x[500010],y[500010];
	cin >> N;
	for(int i = 0;i < N;i++) cin >> x[i];
	for(int i = 0;i < N;i++) cin >> y[i];
	cin >> m;
	cout << init(N,x,y) << endl;
	for(int i = 0;i < m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 1) cout << updateX(b,c) << endl;
		else cout << updateY(b,c) << endl;
	}
	return 0;
}*/

Compilation message

horses.cpp: In member function 'long long int RMQ::find(long long int, long long int, bool)':
horses.cpp:44:16: warning: unused variable 'ans' [-Wunused-variable]
   ll pos = seg,ans = 1000000000;
                ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 2 ms 520 KB Output is correct
7 Correct 3 ms 520 KB Output is correct
8 Correct 2 ms 520 KB Output is correct
9 Correct 2 ms 520 KB Output is correct
10 Correct 3 ms 520 KB Output is correct
11 Correct 2 ms 520 KB Output is correct
12 Correct 3 ms 520 KB Output is correct
13 Correct 2 ms 520 KB Output is correct
14 Correct 2 ms 552 KB Output is correct
15 Correct 2 ms 608 KB Output is correct
16 Correct 2 ms 608 KB Output is correct
17 Correct 2 ms 608 KB Output is correct
18 Correct 3 ms 608 KB Output is correct
19 Correct 3 ms 652 KB Output is correct
20 Correct 3 ms 680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 680 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 3 ms 680 KB Output is correct
6 Correct 3 ms 680 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 740 KB Output is correct
12 Correct 3 ms 744 KB Output is correct
13 Correct 2 ms 744 KB Output is correct
14 Correct 2 ms 772 KB Output is correct
15 Correct 2 ms 772 KB Output is correct
16 Correct 2 ms 772 KB Output is correct
17 Correct 2 ms 772 KB Output is correct
18 Correct 2 ms 772 KB Output is correct
19 Correct 2 ms 772 KB Output is correct
20 Correct 3 ms 772 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 772 KB Output is correct
23 Correct 4 ms 820 KB Output is correct
24 Correct 3 ms 824 KB Output is correct
25 Correct 4 ms 904 KB Output is correct
26 Correct 3 ms 972 KB Output is correct
27 Correct 4 ms 1040 KB Output is correct
28 Correct 4 ms 1040 KB Output is correct
29 Correct 3 ms 1040 KB Output is correct
30 Correct 3 ms 1040 KB Output is correct
31 Correct 3 ms 1056 KB Output is correct
32 Correct 3 ms 1128 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 34396 KB Output is correct
2 Correct 361 ms 37756 KB Output is correct
3 Correct 319 ms 37992 KB Output is correct
4 Correct 357 ms 37992 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 37992 KB Output is correct
2 Correct 2 ms 37992 KB Output is correct
3 Correct 3 ms 37992 KB Output is correct
4 Correct 2 ms 37992 KB Output is correct
5 Correct 2 ms 37992 KB Output is correct
6 Correct 2 ms 37992 KB Output is correct
7 Correct 2 ms 37992 KB Output is correct
8 Correct 2 ms 37992 KB Output is correct
9 Correct 2 ms 37992 KB Output is correct
10 Correct 3 ms 37992 KB Output is correct
11 Correct 2 ms 37992 KB Output is correct
12 Correct 2 ms 37992 KB Output is correct
13 Correct 3 ms 37992 KB Output is correct
14 Correct 2 ms 37992 KB Output is correct
15 Correct 2 ms 37992 KB Output is correct
16 Correct 2 ms 37992 KB Output is correct
17 Correct 2 ms 37992 KB Output is correct
18 Correct 2 ms 37992 KB Output is correct
19 Correct 3 ms 37992 KB Output is correct
20 Correct 3 ms 37992 KB Output is correct
21 Correct 2 ms 37992 KB Output is correct
22 Correct 2 ms 37992 KB Output is correct
23 Correct 3 ms 37992 KB Output is correct
24 Correct 3 ms 37992 KB Output is correct
25 Correct 3 ms 37992 KB Output is correct
26 Correct 3 ms 37992 KB Output is correct
27 Correct 4 ms 37992 KB Output is correct
28 Correct 3 ms 37992 KB Output is correct
29 Correct 3 ms 37992 KB Output is correct
30 Correct 3 ms 37992 KB Output is correct
31 Correct 4 ms 37992 KB Output is correct
32 Correct 4 ms 37992 KB Output is correct
33 Correct 274 ms 41024 KB Output is correct
34 Correct 256 ms 44400 KB Output is correct
35 Correct 279 ms 44400 KB Output is correct
36 Correct 281 ms 44400 KB Output is correct
37 Correct 292 ms 44532 KB Output is correct
38 Correct 258 ms 44532 KB Output is correct
39 Correct 243 ms 44532 KB Output is correct
40 Correct 259 ms 44532 KB Output is correct
41 Correct 238 ms 44532 KB Output is correct
42 Correct 256 ms 44532 KB Output is correct
43 Correct 253 ms 44532 KB Output is correct
44 Correct 243 ms 44532 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 44532 KB Output is correct
2 Correct 2 ms 44532 KB Output is correct
3 Correct 2 ms 44532 KB Output is correct
4 Correct 2 ms 44532 KB Output is correct
5 Correct 2 ms 44532 KB Output is correct
6 Correct 2 ms 44532 KB Output is correct
7 Correct 2 ms 44532 KB Output is correct
8 Correct 3 ms 44532 KB Output is correct
9 Correct 3 ms 44532 KB Output is correct
10 Correct 2 ms 44532 KB Output is correct
11 Correct 2 ms 44532 KB Output is correct
12 Correct 2 ms 44532 KB Output is correct
13 Correct 2 ms 44532 KB Output is correct
14 Correct 2 ms 44532 KB Output is correct
15 Correct 2 ms 44532 KB Output is correct
16 Correct 3 ms 44532 KB Output is correct
17 Correct 2 ms 44532 KB Output is correct
18 Correct 2 ms 44532 KB Output is correct
19 Correct 2 ms 44532 KB Output is correct
20 Correct 2 ms 44532 KB Output is correct
21 Correct 3 ms 44532 KB Output is correct
22 Correct 2 ms 44532 KB Output is correct
23 Correct 3 ms 44532 KB Output is correct
24 Correct 3 ms 44532 KB Output is correct
25 Correct 3 ms 44532 KB Output is correct
26 Correct 3 ms 44532 KB Output is correct
27 Correct 4 ms 44532 KB Output is correct
28 Correct 3 ms 44532 KB Output is correct
29 Correct 3 ms 44532 KB Output is correct
30 Correct 3 ms 44532 KB Output is correct
31 Correct 4 ms 44532 KB Output is correct
32 Correct 4 ms 44532 KB Output is correct
33 Correct 335 ms 47848 KB Output is correct
34 Correct 351 ms 47848 KB Output is correct
35 Correct 336 ms 47848 KB Output is correct
36 Correct 391 ms 47848 KB Output is correct
37 Correct 254 ms 47848 KB Output is correct
38 Correct 235 ms 47848 KB Output is correct
39 Correct 275 ms 47848 KB Output is correct
40 Correct 277 ms 47848 KB Output is correct
41 Correct 272 ms 47848 KB Output is correct
42 Correct 242 ms 47848 KB Output is correct
43 Correct 265 ms 47848 KB Output is correct
44 Correct 256 ms 47848 KB Output is correct
45 Correct 238 ms 47848 KB Output is correct
46 Correct 250 ms 47848 KB Output is correct
47 Correct 249 ms 47848 KB Output is correct
48 Correct 255 ms 47848 KB Output is correct
49 Correct 356 ms 47848 KB Output is correct
50 Correct 342 ms 47848 KB Output is correct
51 Correct 340 ms 47848 KB Output is correct
52 Correct 331 ms 47848 KB Output is correct
53 Correct 509 ms 47848 KB Output is correct
54 Correct 316 ms 51672 KB Output is correct
55 Correct 350 ms 51884 KB Output is correct
56 Correct 389 ms 52652 KB Output is correct
57 Correct 339 ms 52676 KB Output is correct
58 Correct 382 ms 52836 KB Output is correct
59 Correct 275 ms 52836 KB Output is correct