oj.uz

Submission #247754

# Submission time Handle Problem Language Result Execution time Memory
247754 2020-07-12T04:38:13 Z super_j6 Horses (IOI15_horses) C++14
100 / 100
 1076 ms 88432 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string.h>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
//solution
const int mod = 1000000007;
const int k = 2;
const int rv[k] = {1, 0};
function<int(int, int)> f[k] = {
	[](int x, int y){ return (ll)x * y % mod;},
	[](int x, int y){ return max(x, y);}
};
 
struct segTree{
	int l, r;
	segTree *left, *right;
	int val[k];
	
	segTree(int a, int b){
		l = a, r = b;
		if(l != r){
			int mid = (l + r) / 2;
			left = new segTree(l, mid);
			right = new segTree(mid + 1, r);
		}
		memcpy(val, rv, sizeof(val));
	}
	
	void add(int x, int v, int t){
		if(x < l || r < x) return;
		if(l == r){
			val[t] = v;
			return;
		}
		left->add(x, v, t);
		right->add(x, v, t);
		val[t] = f[t](left->val[t], right->val[t]);
	}
	
	int qry(int a, int b, int t){
		if(b < l || r < a) return rv[t];
		if(a <= l && r <= b) return val[t];
		return f[t](left->qry(a, b, t), right->qry(a, b, t));
	}
};
 
const int mxn = 500000;
int n;
int *x, *y;
set<int, greater<int>> s;
segTree tre(0, mxn);
 
void addx(int a, int b){
	if(a){
		if(~-x[a]) s.erase(a);
		if(~-(x[a] = b)) s.insert(a);
	}else{
		x[a] = b;
	}
	tre.add(a, b, 0);
}
 
void addy(int a, int b){
	y[a] = b;
	tre.add(a, b, 1);
}
 
int sol(){
	auto it = ++s.begin();
	__int128 cur, b, ret;
	for(cur = 1; it != s.end() && cur < mod; it++) cur *= x[*it];
	if(it == s.end()) it--;
	for(cur = 1, b = *it, ret = 0; it != s.begin(); it--){
		cur *= x[*it];
		ret = max(ret, cur * tre.qry(*it, *prev(it) - 1, 1));
	}
	return ret % mod * tre.qry(0, b - 1, 0) % mod;
}
//end solution
 
//interaction
int init(int N, int *X, int *Y){
	n = N, x = X, y = Y;
	s.insert(0), s.insert(n);
	for(int i = 0; i < n; i++){
		addx(i, x[i]);
		addy(i, y[i]);
	}
	return sol();
}
 
int updateX(int a, int b){
	addx(a, b);
	return sol();
}
 
int updateY(int a, int b){
	addy(a, b);
	return sol();
}
//end interaction
/*
//test
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int n, q;
	
	cin >> n;
	int x[n], y[n];
	
	for(int i = 0; i < n; i++) cin >> x[i];
	for(int i = 0; i < n; i++) cin >> y[i];
	
	cout << init(n, x, y) << endl;
	
	cin >> q;
	while(q--){
		int t, a, b;
		cin >> t >> a >> b;
		cout << (t == 1 ? updateX(a, b) : updateY(a, b)) << endl;
	}
 
	return 0;
}
//end test
*/

Compilation message

horses.cpp: In function 'int sol()':
horses.cpp:86:34: warning: conversion to 'int' from '__int128' may alter its value [-Wconversion]
  return ret % mod * tre.qry(0, b - 1, 0) % mod;
                                ~~^~~
horses.cpp:86:42: warning: conversion to 'int' from '__int128' may alter its value [-Wconversion]
  return ret % mod * tre.qry(0, b - 1, 0) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47224 KB Output is correct
2 Correct 42 ms 47224 KB Output is correct
3 Correct 43 ms 47224 KB Output is correct
4 Correct 44 ms 47224 KB Output is correct
5 Correct 43 ms 47224 KB Output is correct
6 Correct 51 ms 47224 KB Output is correct
7 Correct 44 ms 47224 KB Output is correct
8 Correct 42 ms 47224 KB Output is correct
9 Correct 42 ms 47224 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 41 ms 47224 KB Output is correct
12 Correct 42 ms 47224 KB Output is correct
13 Correct 43 ms 47224 KB Output is correct
14 Correct 42 ms 47224 KB Output is correct
15 Correct 43 ms 47352 KB Output is correct
16 Correct 43 ms 47224 KB Output is correct
17 Correct 43 ms 47264 KB Output is correct
18 Correct 44 ms 47224 KB Output is correct
19 Correct 43 ms 47224 KB Output is correct
20 Correct 43 ms 47224 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47224 KB Output is correct
2 Correct 46 ms 47224 KB Output is correct
3 Correct 47 ms 47272 KB Output is correct
4 Correct 42 ms 47224 KB Output is correct
5 Correct 42 ms 47224 KB Output is correct
6 Correct 45 ms 47224 KB Output is correct
7 Correct 42 ms 47224 KB Output is correct
8 Correct 42 ms 47224 KB Output is correct
9 Correct 46 ms 47224 KB Output is correct
10 Correct 43 ms 47224 KB Output is correct
11 Correct 50 ms 47204 KB Output is correct
12 Correct 47 ms 47224 KB Output is correct
13 Correct 44 ms 47224 KB Output is correct
14 Correct 43 ms 47224 KB Output is correct
15 Correct 43 ms 47224 KB Output is correct
16 Correct 43 ms 47224 KB Output is correct
17 Correct 44 ms 47404 KB Output is correct
18 Correct 44 ms 47224 KB Output is correct
19 Correct 44 ms 47208 KB Output is correct
20 Correct 42 ms 47224 KB Output is correct
21 Correct 44 ms 47352 KB Output is correct
22 Correct 43 ms 47232 KB Output is correct
23 Correct 44 ms 47352 KB Output is correct
24 Correct 44 ms 47352 KB Output is correct
25 Correct 45 ms 47352 KB Output is correct
26 Correct 44 ms 47352 KB Output is correct
27 Correct 52 ms 47352 KB Output is correct
28 Correct 48 ms 47352 KB Output is correct
29 Correct 44 ms 47352 KB Output is correct
30 Correct 45 ms 47352 KB Output is correct
31 Correct 46 ms 47356 KB Output is correct
32 Correct 50 ms 47352 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 75896 KB Output is correct
2 Correct 790 ms 88244 KB Output is correct
3 Correct 807 ms 79484 KB Output is correct
4 Correct 891 ms 83320 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 43 ms 47224 KB Output is correct
3 Correct 43 ms 47224 KB Output is correct
4 Correct 42 ms 47224 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 41 ms 47224 KB Output is correct
7 Correct 44 ms 47224 KB Output is correct
8 Correct 42 ms 47232 KB Output is correct
9 Correct 45 ms 47228 KB Output is correct
10 Correct 43 ms 47232 KB Output is correct
11 Correct 44 ms 47224 KB Output is correct
12 Correct 43 ms 47224 KB Output is correct
13 Correct 45 ms 47352 KB Output is correct
14 Correct 43 ms 47224 KB Output is correct
15 Correct 44 ms 47224 KB Output is correct
16 Correct 43 ms 47224 KB Output is correct
17 Correct 43 ms 47224 KB Output is correct
18 Correct 44 ms 47312 KB Output is correct
19 Correct 45 ms 47352 KB Output is correct
20 Correct 43 ms 47228 KB Output is correct
21 Correct 43 ms 47228 KB Output is correct
22 Correct 43 ms 47224 KB Output is correct
23 Correct 44 ms 47352 KB Output is correct
24 Correct 44 ms 47352 KB Output is correct
25 Correct 45 ms 47352 KB Output is correct
26 Correct 44 ms 47352 KB Output is correct
27 Correct 49 ms 47352 KB Output is correct
28 Correct 47 ms 47376 KB Output is correct
29 Correct 45 ms 47352 KB Output is correct
30 Correct 44 ms 47352 KB Output is correct
31 Correct 47 ms 47352 KB Output is correct
32 Correct 49 ms 47352 KB Output is correct
33 Correct 332 ms 52092 KB Output is correct
34 Correct 346 ms 52080 KB Output is correct
35 Correct 548 ms 75220 KB Output is correct
36 Correct 566 ms 75136 KB Output is correct
37 Correct 388 ms 52088 KB Output is correct
38 Correct 432 ms 63992 KB Output is correct
39 Correct 328 ms 51836 KB Output is correct
40 Correct 575 ms 75256 KB Output is correct
41 Correct 344 ms 51960 KB Output is correct
42 Correct 362 ms 51960 KB Output is correct
43 Correct 531 ms 75312 KB Output is correct
44 Correct 513 ms 75128 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 42 ms 47224 KB Output is correct
3 Correct 43 ms 47228 KB Output is correct
4 Correct 45 ms 47224 KB Output is correct
5 Correct 46 ms 47224 KB Output is correct
6 Correct 43 ms 47224 KB Output is correct
7 Correct 43 ms 47352 KB Output is correct
8 Correct 43 ms 47224 KB Output is correct
9 Correct 43 ms 47224 KB Output is correct
10 Correct 43 ms 47260 KB Output is correct
11 Correct 44 ms 47224 KB Output is correct
12 Correct 54 ms 47352 KB Output is correct
13 Correct 51 ms 47224 KB Output is correct
14 Correct 42 ms 47224 KB Output is correct
15 Correct 44 ms 47224 KB Output is correct
16 Correct 41 ms 47224 KB Output is correct
17 Correct 44 ms 47224 KB Output is correct
18 Correct 41 ms 47224 KB Output is correct
19 Correct 45 ms 47224 KB Output is correct
20 Correct 53 ms 47316 KB Output is correct
21 Correct 44 ms 47224 KB Output is correct
22 Correct 43 ms 47224 KB Output is correct
23 Correct 53 ms 47288 KB Output is correct
24 Correct 45 ms 47352 KB Output is correct
25 Correct 55 ms 47480 KB Output is correct
26 Correct 45 ms 47352 KB Output is correct
27 Correct 51 ms 47352 KB Output is correct
28 Correct 50 ms 47352 KB Output is correct
29 Correct 45 ms 47352 KB Output is correct
30 Correct 46 ms 47352 KB Output is correct
31 Correct 52 ms 47352 KB Output is correct
32 Correct 49 ms 47352 KB Output is correct
33 Correct 1045 ms 76596 KB Output is correct
34 Correct 808 ms 88432 KB Output is correct
35 Correct 792 ms 79608 KB Output is correct
36 Correct 916 ms 83384 KB Output is correct
37 Correct 350 ms 55416 KB Output is correct
38 Correct 344 ms 55416 KB Output is correct
39 Correct 571 ms 85728 KB Output is correct
40 Correct 566 ms 85716 KB Output is correct
41 Correct 389 ms 53496 KB Output is correct
42 Correct 426 ms 66296 KB Output is correct
43 Correct 336 ms 53368 KB Output is correct
44 Correct 568 ms 80972 KB Output is correct
45 Correct 349 ms 53316 KB Output is correct
46 Correct 377 ms 53408 KB Output is correct
47 Correct 521 ms 81144 KB Output is correct
48 Correct 526 ms 81160 KB Output is correct
49 Correct 563 ms 58676 KB Output is correct
50 Correct 514 ms 58360 KB Output is correct
51 Correct 738 ms 87600 KB Output is correct
52 Correct 666 ms 87172 KB Output is correct
53 Correct 1076 ms 56668 KB Output is correct
54 Correct 649 ms 70264 KB Output is correct
55 Correct 497 ms 54356 KB Output is correct
56 Correct 688 ms 82680 KB Output is correct
57 Correct 664 ms 55100 KB Output is correct
58 Correct 830 ms 55544 KB Output is correct
59 Correct 526 ms 81144 KB Output is correct