oj.uz

Submission #398539

# Submission time Handle Problem Language Result Execution time Memory
398539 2021-05-04T13:42:57 Z cfalas Horses (IOI15_horses) C++14
100 / 100
 797 ms 100632 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007ll
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

ll mpow(ll a, ll b){
	if(b==0) return 1;
	if(b==1) return a;
	ll z = mpow(a, b/2);
	z*=z;
	z%=MOD;
	if(b%2) z*=a;
	return z%MOD;
}

ll modinv(ll x){
	return mpow(x, MOD-2);
}
struct seg_tree{
	typedef long double T;
	struct node{
		T val;
		T laz;
		ll val_mod;
		ll laz_mod=1;
		int left=-1;
		int right=-1;
		node() {val=0, laz=0, left=-1, right=-1;}
		node(T v, ll q) {val=v, val_mod=q, laz=0, laz_mod=1, right=-1, left=-1;}
		node(T v) {val=v, val_mod=0, laz=0, laz_mod=1, right=-1, left=-1;}
	};
	vector<node> seg;
	static inline int N;
	const int RAND_VALUE=0;
	seg_tree(int n){N=n, seg.assign(1, node());}

	inline node merge(node par, node a, node b){
		node ret;
		ret.left = par.left, ret.right = par.right;
		ret.val = max(a.val, b.val);
		if(a.val>b.val) ret.val_mod = a.val_mod;
		else ret.val_mod = b.val_mod;
		return ret;
	}

	inline void update_node(ll ind, ll val, ll val_prev, int l, int r){
		//cout<<"change "<<l<<" "<<r<<" by "<<log(val)<<" "<<log(val_prev)<<endl;
		seg[ind].val += (log(val)-log(val_prev));
		seg[ind].val_mod = ((seg[ind].val_mod * modinv(val_prev))%MOD * val)%MOD;
		seg[ind].laz += (log(val)-log(val_prev));
		seg[ind].laz_mod *= (modinv(val_prev) * val)%MOD;
		seg[ind].laz_mod %= MOD;
	}

	inline void down(node &par, int l, int r){
		if(par.laz && par.laz_mod!=1){
			seg[par.left].val += par.laz;
			seg[par.right].val += par.laz;

			seg[par.left].laz += par.laz;
			seg[par.right].laz += par.laz;

			seg[par.left].val_mod = (seg[par.left].val_mod * par.laz_mod)%MOD;
			seg[par.right].val_mod = (seg[par.right].val_mod * par.laz_mod)%MOD;

			seg[par.left].laz_mod *= par.laz_mod;
			seg[par.left].laz_mod %= MOD;
			seg[par.right].laz_mod *= par.laz_mod;
			seg[par.right].laz_mod %= MOD;
		}

		par.laz = 0;
		par.laz_mod = 1;
	}

	inline void create_children(int ind){
		node par = seg[ind];
		if(par.left==-1) par.left=seg.size(), seg.push_back(node());
		if(par.right==-1) par.right=seg.size(), seg.push_back(node());
		seg[ind] = par;
	}

	void build(vector<T>& arr, vector<ll>& arr_mod, int l=0, int r=N-1, int ind=0){
		if(l==r) seg[ind] = node(arr[l], arr_mod[l]);
		else{
			create_children(ind);
			build(arr,arr_mod, l,MID,seg[ind].left);
			build(arr,arr_mod, MID+1,r,seg[ind].right);

			seg[ind] = merge(seg[ind], seg[seg[ind].left], seg[seg[ind].right]);
		}
	}

	void update(int rl, int rr, ll val, ll val_prev, int l=0, int r=N-1, int ind=0){
		if(rl<=l && r<=rr) update_node(ind, val, val_prev,l,r);
		else if(rr<l || r<rl) return;
		else{
			create_children(ind);
			down(seg[ind],l,r);
			update(rl,rr,val, val_prev,l,MID,seg[ind].left);
			update(rl,rr,val, val_prev, MID+1,r,seg[ind].right);
			seg[ind] = merge(seg[ind], seg[seg[ind].left], seg[seg[ind].right]);
		}
	}

	node _query(int rl, int rr, int l=0, int r=N-1, int ind=0){
		if(rl<=l && r<=rr) return seg[ind];
		else if(rl>r || l>rr) return RAND_VALUE;
		else{
			create_children(ind);
			down(seg[ind],l,r);
			return merge(seg[ind], _query(rl, rr, l, MID, seg[ind].left), _query(rl,rr,MID+1,r,seg[ind].right));
		}
	}

	ll query(int l, int r){
		return _query(l,r).val_mod;
	}
	
};


int n;
vi x,y;
seg_tree seg(n);
int init(int N, int X[], int Y[]) {
	n = N;
	seg.N = n;
	x.resize(n);
	y.resize(n);
	FOR(i,n) x[i] = X[i], y[i] = Y[i];
	vector<long double> ly(n);
	vi my(n);
	ly[0] = log(x[0]);
	my[0] = x[0];
	FORi(i,1,n) ly[i] = ly[i-1] + log(x[i]);
	FORi(i,1,n) my[i] = (my[i-1] * x[i])%MOD;
	FOR(i,n) my[i] = (my[i]*y[i])%MOD;
	FOR(i,n) ly[i] += log(y[i]);
	seg.build(ly, my);
	return seg.query(0, n-1);
}

int updateX(int pos, int val) {	
	ll pval = x[pos];
	x[pos] = val;
	seg.update(pos, n-1, val, pval);
	return seg.query(0, n-1);
}

int updateY(int pos, int val) {
	ll pval = y[pos];
	y[pos] = val;
	seg.update(pos, pos, val, pval);
	return seg.query(0, n-1);
}

Compilation message

horses.cpp:51:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
   51 |  static inline int N;
      |         ^~~~~~
horses.cpp: In member function 'void seg_tree::update_node(long long int, long long int, long long int, int, int)':
horses.cpp:64:59: warning: unused parameter 'l' [-Wunused-parameter]
   64 |  inline void update_node(ll ind, ll val, ll val_prev, int l, int r){
      |                                                       ~~~~^
horses.cpp:64:66: warning: unused parameter 'r' [-Wunused-parameter]
   64 |  inline void update_node(ll ind, ll val, ll val_prev, int l, int r){
      |                                                              ~~~~^
horses.cpp: In member function 'void seg_tree::down(seg_tree::node&, int, int)':
horses.cpp:73:34: warning: unused parameter 'l' [-Wunused-parameter]
   73 |  inline void down(node &par, int l, int r){
      |                              ~~~~^
horses.cpp:73:41: warning: unused parameter 'r' [-Wunused-parameter]
   73 |  inline void down(node &par, int l, int r){
      |                                     ~~~~^
horses.cpp: In member function 'void seg_tree::create_children(int)':
horses.cpp:96:37: warning: conversion from 'std::vector<seg_tree::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   96 |   if(par.left==-1) par.left=seg.size(), seg.push_back(node());
      |                             ~~~~~~~~^~
horses.cpp:97:39: warning: conversion from 'std::vector<seg_tree::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   97 |   if(par.right==-1) par.right=seg.size(), seg.push_back(node());
      |                               ~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:159:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  159 |  return seg.query(0, n-1);
      |         ~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:166:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  166 |  return seg.query(0, n-1);
      |         ~~~~~~~~~^~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:173:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  173 |  return seg.query(0, n-1);
      |         ~~~~~~~~~^~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 89548 KB Output is correct
2 Correct 623 ms 100632 KB Output is correct
3 Correct 581 ms 91748 KB Output is correct
4 Correct 787 ms 95480 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 3 ms 588 KB Output is correct
24 Correct 3 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 3 ms 588 KB Output is correct
28 Correct 4 ms 588 KB Output is correct
29 Correct 3 ms 588 KB Output is correct
30 Correct 4 ms 592 KB Output is correct
31 Correct 2 ms 592 KB Output is correct
32 Correct 3 ms 588 KB Output is correct
33 Correct 198 ms 89576 KB Output is correct
34 Correct 198 ms 93416 KB Output is correct
35 Correct 209 ms 100468 KB Output is correct
36 Correct 240 ms 100344 KB Output is correct
37 Correct 168 ms 91624 KB Output is correct
38 Correct 211 ms 92548 KB Output is correct
39 Correct 170 ms 91552 KB Output is correct
40 Correct 214 ms 95556 KB Output is correct
41 Correct 144 ms 91624 KB Output is correct
42 Correct 164 ms 91696 KB Output is correct
43 Correct 165 ms 95860 KB Output is correct
44 Correct 167 ms 95956 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 268 KB Output is correct
23 Correct 3 ms 588 KB Output is correct
24 Correct 3 ms 588 KB Output is correct
25 Correct 2 ms 588 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 3 ms 588 KB Output is correct
28 Correct 3 ms 588 KB Output is correct
29 Correct 3 ms 588 KB Output is correct
30 Correct 4 ms 588 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 3 ms 588 KB Output is correct
33 Correct 311 ms 89576 KB Output is correct
34 Correct 649 ms 100536 KB Output is correct
35 Correct 591 ms 91752 KB Output is correct
36 Correct 797 ms 95500 KB Output is correct
37 Correct 210 ms 93520 KB Output is correct
38 Correct 209 ms 93416 KB Output is correct
39 Correct 228 ms 100364 KB Output is correct
40 Correct 252 ms 100320 KB Output is correct
41 Correct 179 ms 91644 KB Output is correct
42 Correct 220 ms 92700 KB Output is correct
43 Correct 185 ms 91624 KB Output is correct
44 Correct 225 ms 95444 KB Output is correct
45 Correct 160 ms 91624 KB Output is correct
46 Correct 167 ms 91580 KB Output is correct
47 Correct 173 ms 95868 KB Output is correct
48 Correct 176 ms 95856 KB Output is correct
49 Correct 560 ms 93644 KB Output is correct
50 Correct 574 ms 93580 KB Output is correct
51 Correct 373 ms 100584 KB Output is correct
52 Correct 626 ms 100500 KB Output is correct
53 Correct 512 ms 91732 KB Output is correct
54 Correct 618 ms 92648 KB Output is correct
55 Correct 556 ms 91656 KB Output is correct
56 Correct 672 ms 95680 KB Output is correct
57 Correct 304 ms 91768 KB Output is correct
58 Correct 389 ms 91632 KB Output is correct
59 Correct 174 ms 95976 KB Output is correct