oj.uz

Submission #422622

# Submission time Handle Problem Language Result Execution time Memory
422622 2021-06-10T09:19:32 Z vanic Horses (IOI15_horses) C++14
100 / 100
 756 ms 87336 KB 
#include "horses.h"
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

typedef long long ll;

#define double long double

const int mod=1e9+7, Log=30, maxn=5e5, Log1=19, pot=(1<<Log1);

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}

inline int mul(int a, int b){
	return (ll)a*b%mod;
}

inline int pote(int a, int b){
	int sol=1;
	for(int i=0; i<Log; i++){
		if((1<<i)&b){
			sol=mul(sol, a);
		}
		a=mul(a, a);
	}
	return sol;
}

inline int dij(int a, int b){
	return mul(a, pote(b, mod-2));
}

pair < double, int > t[pot*2];
pair < double, int > prop[pot*2];
int a[maxn];
int b[maxn];

void precompute(){
	for(int i=1; i<pot*2; i++){
		prop[i]={0, 1};
		t[i]={0, 1};
	}
}

void propagate(int x){
	if(prop[x].second==1){
		return;
	}
	t[x].second=mul(t[x].second, prop[x].second);
	t[x].first=t[x].first+prop[x].first;
	if(x<pot){
		prop[x*2]={prop[x*2].first+prop[x].first, mul(prop[x*2].second, prop[x].second)};
		prop[x*2+1]={prop[x*2+1].first+prop[x].first, mul(prop[x*2+1].second, prop[x].second)};
	}
	prop[x]={0, 1};
}

void update(int L, int D, int x, int l, int d, double val1, int val2){
	propagate(x);
	if(L>=l && D<=d){
		t[x]={t[x].first+val1, mul(t[x].second, val2)};
//		cout << "upd " << x-pot << ' ' << t[x] << endl;
		if(x<pot){
			prop[x*2]={prop[x*2].first+val1, mul(prop[x*2].second, val2)};
			prop[x*2+1]={prop[x*2+1].first+val1, mul(prop[x*2+1].second, val2)};
		}
		return;
	}
	if((L+D)/2>=l){
		update(L, (L+D)/2, x*2, l, d, val1, val2);
	}
	if((L+D)/2+1<=d){
		update((L+D)/2+1, D, x*2+1, l, d, val1, val2);
	}
	propagate(x*2);
	propagate(x*2+1);
	if(t[x*2].first>t[x*2+1].first){
		t[x]=t[x*2];
	}
	else{
		t[x]=t[x*2+1];
	}
}

int init(int n, int x[], int y[]){
	precompute();
	int val=1;
	double val1=0;
	for(int i=0; i<pot; i++){
		if(i<n){
			a[i]=x[i];
			b[i]=y[i];
			val=mul(val, a[i]);
			val1+=log(a[i]);
			update(0, pot-1, 1, i, i, val1+log(b[i]),  mul(val, b[i]));
		}
		else{
			update(0, pot-1, 1, i, i, val1, val);
		}
	}
	return t[1].second;
}

int updateX(int pos, int val){
	update(0, pot-1, 1, pos, pot-1, log(val)-log(a[pos]), dij(val, a[pos]));
	a[pos]=val;
	return t[1].second;
}

int updateY(int pos, int val){
//	cout << "val " << b[pos] << ' ' << val << endl;
	update(0, pot-1, 1, pos, pos, log(val)-log(b[pos]), dij(val, b[pos]));
	b[pos]=val;
	return t[1].second;
}
/*

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	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) << '\n';
	int q;
	cin >> q;
	int a1, b1, c1;
	for(int i=0; i<q; i++){
		cin >> a1 >> b1 >> c1;
		if(a1==1){
			cout << updateX(b1, c1) << '\n';
		}
		else{
			cout << updateY(b1, c1) << '\n';
		}
	}
	return 0;
}
*/

Compilation message

horses.cpp: In function 'int mul(int, int)':
horses.cpp:25:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   25 |  return (ll)a*b%mod;
      |         ~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 65864 KB Output is correct
2 Correct 308 ms 65948 KB Output is correct
3 Correct 307 ms 65952 KB Output is correct
4 Correct 306 ms 65952 KB Output is correct
5 Correct 343 ms 65956 KB Output is correct
6 Correct 359 ms 65888 KB Output is correct
7 Correct 307 ms 65956 KB Output is correct
8 Correct 308 ms 66064 KB Output is correct
9 Correct 303 ms 65988 KB Output is correct
10 Correct 308 ms 66000 KB Output is correct
11 Correct 306 ms 65976 KB Output is correct
12 Correct 304 ms 66016 KB Output is correct
13 Correct 311 ms 65952 KB Output is correct
14 Correct 304 ms 65956 KB Output is correct
15 Correct 307 ms 65960 KB Output is correct
16 Correct 310 ms 65868 KB Output is correct
17 Correct 338 ms 65860 KB Output is correct
18 Correct 303 ms 65868 KB Output is correct
19 Correct 340 ms 65864 KB Output is correct
20 Correct 312 ms 65936 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 65988 KB Output is correct
2 Correct 311 ms 65916 KB Output is correct
3 Correct 307 ms 65952 KB Output is correct
4 Correct 303 ms 65888 KB Output is correct
5 Correct 318 ms 66016 KB Output is correct
6 Correct 317 ms 66000 KB Output is correct
7 Correct 310 ms 65952 KB Output is correct
8 Correct 305 ms 65984 KB Output is correct
9 Correct 306 ms 65952 KB Output is correct
10 Correct 308 ms 65984 KB Output is correct
11 Correct 304 ms 66056 KB Output is correct
12 Correct 300 ms 65952 KB Output is correct
13 Correct 339 ms 65944 KB Output is correct
14 Correct 303 ms 66056 KB Output is correct
15 Correct 308 ms 65956 KB Output is correct
16 Correct 305 ms 66056 KB Output is correct
17 Correct 348 ms 65860 KB Output is correct
18 Correct 303 ms 65924 KB Output is correct
19 Correct 309 ms 65968 KB Output is correct
20 Correct 311 ms 65960 KB Output is correct
21 Correct 308 ms 65956 KB Output is correct
22 Correct 340 ms 65952 KB Output is correct
23 Correct 323 ms 65988 KB Output is correct
24 Correct 325 ms 65988 KB Output is correct
25 Correct 326 ms 66000 KB Output is correct
26 Correct 329 ms 65992 KB Output is correct
27 Correct 318 ms 65980 KB Output is correct
28 Correct 322 ms 66068 KB Output is correct
29 Correct 335 ms 65980 KB Output is correct
30 Correct 303 ms 65988 KB Output is correct
31 Correct 307 ms 65960 KB Output is correct
32 Correct 334 ms 65988 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 74852 KB Output is correct
2 Correct 709 ms 87336 KB Output is correct
3 Correct 654 ms 78660 KB Output is correct
4 Correct 674 ms 82460 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 65948 KB Output is correct
2 Correct 315 ms 65864 KB Output is correct
3 Correct 311 ms 65860 KB Output is correct
4 Correct 308 ms 65928 KB Output is correct
5 Correct 312 ms 65948 KB Output is correct
6 Correct 318 ms 66008 KB Output is correct
7 Correct 358 ms 65932 KB Output is correct
8 Correct 314 ms 65956 KB Output is correct
9 Correct 315 ms 65960 KB Output is correct
10 Correct 315 ms 65960 KB Output is correct
11 Correct 308 ms 65952 KB Output is correct
12 Correct 331 ms 65956 KB Output is correct
13 Correct 325 ms 65956 KB Output is correct
14 Correct 338 ms 65952 KB Output is correct
15 Correct 332 ms 65960 KB Output is correct
16 Correct 326 ms 65956 KB Output is correct
17 Correct 329 ms 65860 KB Output is correct
18 Correct 317 ms 65952 KB Output is correct
19 Correct 329 ms 65860 KB Output is correct
20 Correct 332 ms 65956 KB Output is correct
21 Correct 326 ms 65988 KB Output is correct
22 Correct 316 ms 66012 KB Output is correct
23 Correct 313 ms 65984 KB Output is correct
24 Correct 306 ms 66052 KB Output is correct
25 Correct 307 ms 66076 KB Output is correct
26 Correct 305 ms 65996 KB Output is correct
27 Correct 306 ms 65984 KB Output is correct
28 Correct 308 ms 65984 KB Output is correct
29 Correct 308 ms 65988 KB Output is correct
30 Correct 305 ms 65988 KB Output is correct
31 Correct 307 ms 66016 KB Output is correct
32 Correct 300 ms 65980 KB Output is correct
33 Correct 430 ms 77792 KB Output is correct
34 Correct 398 ms 77724 KB Output is correct
35 Correct 400 ms 84856 KB Output is correct
36 Correct 388 ms 84604 KB Output is correct
37 Correct 364 ms 75980 KB Output is correct
38 Correct 359 ms 76868 KB Output is correct
39 Correct 341 ms 75812 KB Output is correct
40 Correct 380 ms 79684 KB Output is correct
41 Correct 387 ms 75800 KB Output is correct
42 Correct 344 ms 75876 KB Output is correct
43 Correct 362 ms 80092 KB Output is correct
44 Correct 367 ms 80148 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 65988 KB Output is correct
2 Correct 332 ms 65952 KB Output is correct
3 Correct 303 ms 65952 KB Output is correct
4 Correct 320 ms 65960 KB Output is correct
5 Correct 307 ms 65948 KB Output is correct
6 Correct 336 ms 66048 KB Output is correct
7 Correct 308 ms 65860 KB Output is correct
8 Correct 343 ms 65956 KB Output is correct
9 Correct 301 ms 65952 KB Output is correct
10 Correct 306 ms 65960 KB Output is correct
11 Correct 305 ms 65952 KB Output is correct
12 Correct 298 ms 65928 KB Output is correct
13 Correct 315 ms 65952 KB Output is correct
14 Correct 302 ms 65968 KB Output is correct
15 Correct 312 ms 65960 KB Output is correct
16 Correct 315 ms 65956 KB Output is correct
17 Correct 303 ms 65956 KB Output is correct
18 Correct 329 ms 65956 KB Output is correct
19 Correct 310 ms 65988 KB Output is correct
20 Correct 309 ms 66056 KB Output is correct
21 Correct 302 ms 65896 KB Output is correct
22 Correct 303 ms 65956 KB Output is correct
23 Correct 310 ms 65988 KB Output is correct
24 Correct 314 ms 66104 KB Output is correct
25 Correct 307 ms 65996 KB Output is correct
26 Correct 303 ms 66008 KB Output is correct
27 Correct 321 ms 65988 KB Output is correct
28 Correct 308 ms 65980 KB Output is correct
29 Correct 307 ms 65992 KB Output is correct
30 Correct 306 ms 65988 KB Output is correct
31 Correct 338 ms 66108 KB Output is correct
32 Correct 306 ms 65992 KB Output is correct
33 Correct 439 ms 78556 KB Output is correct
34 Correct 756 ms 87256 KB Output is correct
35 Correct 687 ms 78460 KB Output is correct
36 Correct 690 ms 82340 KB Output is correct
37 Correct 405 ms 77760 KB Output is correct
38 Correct 394 ms 77892 KB Output is correct
39 Correct 396 ms 84700 KB Output is correct
40 Correct 396 ms 84624 KB Output is correct
41 Correct 383 ms 75972 KB Output is correct
42 Correct 367 ms 76796 KB Output is correct
43 Correct 340 ms 75840 KB Output is correct
44 Correct 379 ms 79740 KB Output is correct
45 Correct 348 ms 75844 KB Output is correct
46 Correct 356 ms 75920 KB Output is correct
47 Correct 367 ms 80156 KB Output is correct
48 Correct 376 ms 80180 KB Output is correct
49 Correct 695 ms 79880 KB Output is correct
50 Correct 702 ms 79988 KB Output is correct
51 Correct 518 ms 86516 KB Output is correct
52 Correct 520 ms 86196 KB Output is correct
53 Correct 625 ms 78184 KB Output is correct
54 Correct 488 ms 78616 KB Output is correct
55 Correct 438 ms 76840 KB Output is correct
56 Correct 547 ms 81476 KB Output is correct
57 Correct 422 ms 77512 KB Output is correct
58 Correct 451 ms 78072 KB Output is correct
59 Correct 363 ms 80128 KB Output is correct