oj.uz

Submission #140512

# Submission time Handle Problem Language Result Execution time Memory
140512 2019-08-03T09:30:25 Z SirCeness Horses (IOI15_horses) C++14
100 / 100
 880 ms 47480 KB 
#include "horses.h"
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define orta ((l+r)>>1)
using namespace std;
typedef long long ll;

double arr[500005];
ll arrmod[500005];
int st[4*500005];
ll stmod[4*500005];
double lazy[4*500005];
int n;
int x[500005];
int y[500005];

ll us(ll a, ll b){
	ll ans = 1;
	while (b){
		if (b & 1){
			ans *= a;
			ans %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return ans;
}

ll inv(ll a){
	return us(a, mod-2);
}

void push(int node){
	lazy[node*2] += lazy[node];
	lazy[node*2+1] += lazy[node];
	lazy[node] = 0;
}

int get(int node){
	push(node);
	return st[node];
}

double getval(int node, int l, int r, int ind){
	if (l == r) return lazy[node] + arr[l];
	else {
		if (ind <= orta){
			return getval(node*2, l, orta, ind) + lazy[node];
		} else return getval(node*2+1, orta+1, r, ind) + lazy[node];
	}
}

void stc(int node, int l, int r){
	if (l == r){
		lazy[node] = 0;
		st[node] = l;
	} else {
		int m = orta;
		stc(node*2, l, m);
		stc(node*2+1, m+1, r);
		double val1 = getval(1, 0, n-1, st[node*2]);
		double val2 = getval(1, 0, n-1, st[node*2+1]);
		st[node] = (val1 > val2) ? st[node*2] : st[node*2+1];
		lazy[node] = 0;
	}
}

int stq(int node, int l, int r, int sl, int sr){
	if (inside) return get(node);
	else if (outside) return 0;
	else {
		push(node);
		int m = orta;
		int i1 = stq(node*2, l, m, sl, sr);
		int i2 = stq(node*2+1, m+1, r, sl, sr);
		return getval(1, 0, n-1, i1) > getval(1, 0, n-1, i2) ? i1 : i2;
	}
}

void stu(int node, int l, int r, int ind, double val){
	if (l == r) arr[l] += val;
	else {
		push(node);
		int m = orta;
		if (ind <= m) stu(node*2, l, m, ind, val);
		else stu(node*2+1, m+1, r, ind, val);
		
		double val1 = getval(1, 0, n-1, st[node*2]);
		double val2 = getval(1, 0, n-1, st[node*2+1]);
		st[node] = (val1 > val2) ? st[node*2] : st[node*2+1];
	}
}

void stul(int node, int l, int r, int sl, int sr, double val){
	if (inside) lazy[node] += val;
	else if (outside) return;
	else {
		int m = orta;
		push(node);
		stul(node*2, l, m, sl, sr, val);
		stul(node*2+1, m+1, r, sl, sr, val);
		
		double val1 = getval(1, 0, n-1, st[node*2]);
		double val2 = getval(1, 0, n-1, st[node*2+1]);
		st[node] = (val1 > val2) ? st[node*2] : st[node*2+1];
	}
}

void stcmod(int node, int l, int r){
	if (l == r) stmod[node] = arrmod[l];
	else {
		int m = orta;
		stcmod(node*2, l, m);
		stcmod(node*2+1, m+1, r);
		stmod[node] = 1;
	}
}

void stumod(int node, int l, int r, int sl, int sr, ll val){
	if (inside) stmod[node] = (stmod[node]*val)%mod;
	else if (outside) return;
	else {
		int m = orta;
		stumod(node*2, l, m, sl, sr, val);
		stumod(node*2+1, m+1, r, sl, sr, val);
	}
}

ll stqmod(int node, int l, int r, int ind){
	if (l == r) return stmod[node];
	else {
		if (ind <= orta) return (stmod[node]*stqmod(node*2, l, orta, ind))%mod;
		else return (stmod[node]*stqmod(node*2+1, orta+1, r, ind))%mod;
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) x[i] = X[i];
	for (int i = 0; i < n; i++) y[i] = Y[i];
	double sum = 0;
	ll summod = 1;
	for (int i = 0; i < n; i++){
		sum += log2(X[i]);
		arr[i] = sum + log2(Y[i]);
		
		summod *= X[i];
		summod %= mod;
		arrmod[i] = (summod*Y[i])%mod;
		
	}
		
	//prarr(arr, n);
	
	stc(1, 0, n-1);
	stcmod(1, 0, n-1);
	
	//for (int i = 0; i < 3; i++) cout << stqmod(1, 0, n-1, i) << " "; cout << endl;
	//for (int i = 0; i < 3; i++) cout << getval(1, 0, n-1, i) << " "; cout << endl;
	
	return stqmod(1, 0, n-1, stq(1, 0, n-1, 0, n-1));
}

int updateX(int pos, int val){
	stul(1, 0, n-1, pos, n-1, log2(val)-log2(x[pos]));
	stumod(1, 0, n-1, pos, n-1, ((ll)val*inv(x[pos]))%mod);
	/*for (int i = pos; i < n; i++){
		arrmod[i] *= inv(x[pos]);
		arrmod[i] %= mod;
		arrmod[i] *= (ll)val;
		arrmod[i] %= mod;
	}*/
	x[pos] = val;
	return stqmod(1, 0, n-1, stq(1, 0, n-1, 0, n-1));
}

int updateY(int pos, int val) {
	//cout << "update " << pos << " -> " << log2(val) - log2(y[pos]) << endl;
	stu(1, 0, n-1, pos, log2(val) - log2(y[pos]));
	//prarr(arr, 3);
	//for (int i = 0; i < 3; i++) cout << getval(1, 0, n-1, i) << " "; cout << endl;
	/*arrmod[pos] *= inv(y[pos]);
	arrmod[pos] %= mod;
	arrmod[pos] *= val;
	arrmod[pos] %= mod;*/
	stumod(1, 0, n-1, pos, pos, ((ll)val*inv(y[pos]))%mod);
	y[pos] = val;
	
	return stqmod(1, 0, n-1, stq(1, 0, n-1, 0, n-1));
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:174:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return stqmod(1, 0, n-1, stq(1, 0, n-1, 0, n-1));
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:187:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return stqmod(1, 0, n-1, stq(1, 0, n-1, 0, n-1));
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:202:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return stqmod(1, 0, n-1, stq(1, 0, n-1, 0, n-1));
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 37760 KB Output is correct
2 Correct 833 ms 41604 KB Output is correct
3 Correct 808 ms 41368 KB Output is correct
4 Correct 799 ms 45304 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 4 ms 504 KB Output is correct
24 Correct 4 ms 504 KB Output is correct
25 Correct 4 ms 504 KB Output is correct
26 Correct 4 ms 476 KB Output is correct
27 Correct 4 ms 504 KB Output is correct
28 Correct 4 ms 504 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 4 ms 504 KB Output is correct
31 Correct 4 ms 504 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 258 ms 39884 KB Output is correct
34 Correct 273 ms 40696 KB Output is correct
35 Correct 254 ms 47480 KB Output is correct
36 Correct 255 ms 45732 KB Output is correct
37 Correct 235 ms 38776 KB Output is correct
38 Correct 224 ms 39712 KB Output is correct
39 Correct 205 ms 38648 KB Output is correct
40 Correct 234 ms 42564 KB Output is correct
41 Correct 217 ms 38648 KB Output is correct
42 Correct 213 ms 38752 KB Output is correct
43 Correct 197 ms 42932 KB Output is correct
44 Correct 199 ms 42836 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 4 ms 504 KB Output is correct
24 Correct 4 ms 504 KB Output is correct
25 Correct 4 ms 504 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 4 ms 504 KB Output is correct
28 Correct 4 ms 504 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 4 ms 504 KB Output is correct
31 Correct 4 ms 508 KB Output is correct
32 Correct 3 ms 504 KB Output is correct
33 Correct 561 ms 39196 KB Output is correct
34 Correct 880 ms 40184 KB Output is correct
35 Correct 837 ms 41380 KB Output is correct
36 Correct 793 ms 45304 KB Output is correct
37 Correct 256 ms 40644 KB Output is correct
38 Correct 255 ms 40548 KB Output is correct
39 Correct 254 ms 46160 KB Output is correct
40 Correct 253 ms 47480 KB Output is correct
41 Correct 234 ms 38776 KB Output is correct
42 Correct 224 ms 39804 KB Output is correct
43 Correct 203 ms 38680 KB Output is correct
44 Correct 231 ms 42616 KB Output is correct
45 Correct 216 ms 38680 KB Output is correct
46 Correct 211 ms 38776 KB Output is correct
47 Correct 196 ms 43040 KB Output is correct
48 Correct 195 ms 42872 KB Output is correct
49 Correct 868 ms 42580 KB Output is correct
50 Correct 849 ms 42596 KB Output is correct
51 Correct 606 ms 46424 KB Output is correct
52 Correct 604 ms 46080 KB Output is correct
53 Correct 823 ms 41080 KB Output is correct
54 Correct 589 ms 41524 KB Output is correct
55 Correct 501 ms 39640 KB Output is correct
56 Correct 612 ms 44408 KB Output is correct
57 Correct 620 ms 40440 KB Output is correct
58 Correct 579 ms 40824 KB Output is correct
59 Correct 198 ms 42980 KB Output is correct