oj.uz

Submission #984230

# Submission time Handle Problem Language Result Execution time Memory
984230 2024-05-16T11:52:54 Z SmuggingSpun Horses (IOI15_horses) C++14
77 / 100
 1500 ms 44352 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int lim = 5e5 + 5;
int power(int a, int b){
	int ans = 1;
	for(; b > 0; b >>= 1, a = 1LL * a * a % mod){
		if(b & 1){
			ans = 1LL * ans * a % mod;
		}
	}
	return ans;
}
int n, pl[lim << 2], pr[lim << 2], temp[lim << 2], st[lim << 2], x[lim], x_st[lim << 2], y[lim], bit[lim];
int get_bit(int p){
	int ans = 1;
	for(; p > 0; p -= p & -p){
		ans = 1LL * ans * bit[p] % mod;
	}
	return ans;
}
void update_bit(int p, int x){
	for(; p <= n; p += p & -p){
		bit[p] = 1LL * bit[p] * x % mod;
	}
}
int get_x_prod(int id, int l, int r, int u, int v){
	if(l > v || r < u){
		return 1;
	}
	if(u <= l && v >= r){
		return x_st[id];
	}
	int m = (l + r) >> 1, left = get_x_prod(id << 1, l, m, u, v);
	if(left == mod){
		return mod;
	}
	return min(ll(mod), 1LL * left * get_x_prod(id << 1 | 1, m + 1, r, u, v));
}
int merge(int id){
	int l = st[id << 1], r = st[id << 1 | 1];
	if(l == 0){
		return r;
	}
	if(r == 0){
		return l;
	}
	if(pl[id] != l || pr[id] != r){
		temp[id] = get_x_prod(1, 1, n, l + 1, r); 
	}
	return 1LL * temp[id] * y[r] < ll(y[l]) ? l : r;
}
void update_X(int id, int l, int r, int p, int X){
	if(l == r){
		update_bit(l, 1LL * power(x[l], mod - 2) * X % mod);
		x[st[id] = l] = X;
		x_st[id] = X;
		return;
	}
	int m = (l + r) >> 1;
	if(m < p){
		update_X(id << 1 | 1, m + 1, r, p, X);
	}
	else{
		update_X(id << 1, l, m, p, X);
	}
	st[id] = merge(id);
	x_st[id] = min(ll(mod), 1LL * x_st[id << 1] * x_st[id << 1 | 1]);
}
void update_Y(int p, int Y){
	y[p] = Y;
	int id = 1, l = 1, r = n;
	while(l < r){
		int m = (l + r) >> 1;
		id <<= 1;
		if(m < p){
			l = m + 1;
			id |= 1;
		}
		else{
			r = m;
		}
	}
	while((id >>= 1) > 0){
		st[id] = merge(id);
	}
}
int init(int N, int X[], int Y[]){
	n = N;
	fill(bit, bit + lim, 1);
	for(int i = 1; i <= n; i++){
		y[i] = Y[i - 1];
		update_bit(i, x[i] = X[i - 1]);
	}
	memset(pl, -1, sizeof(pl));
	memset(pr, -1, sizeof(pr));
	fill(x_st, x_st + (lim << 2), 1);
	for(int i = 1; i <= n; i++){
		update_X(1, 1, n, i, X[i - 1]);
	}
	return 1LL * get_bit(st[1]) * y[st[1]] % mod;
}
int updateX(int pos, int val){	
	update_X(1, 1, n, pos + 1, val);
	return 1LL * get_bit(st[1]) * y[st[1]] % mod;
}
int updateY(int pos, int val){
	update_Y(pos + 1, val);
	return 1LL * get_bit(st[1]) * y[st[1]] % mod;
}

Compilation message

horses.cpp: In function 'int power(int, int)':
horses.cpp:9:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    9 |  for(; b > 0; b >>= 1, a = 1LL * a * a % mod){
      |                            ~~~~~~~~~~~~^~~~~
horses.cpp:11:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |    ans = 1LL * ans * a % mod;
      |          ~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get_bit(int)':
horses.cpp:20:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |   ans = 1LL * ans * bit[p] % mod;
      |         ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update_bit(int, int)':
horses.cpp:24:28: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   24 | void update_bit(int p, int x){
      |                        ~~~~^
horses.cpp:16:66: note: shadowed declaration is here
   16 | int n, pl[lim << 2], pr[lim << 2], temp[lim << 2], st[lim << 2], x[lim], x_st[lim << 2], y[lim], bit[lim];
      |                                                                  ^
horses.cpp:26:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   26 |   bit[p] = 1LL * bit[p] * x % mod;
      |            ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get_x_prod(int, int, int, int, int)':
horses.cpp:40:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |  return min(ll(mod), 1LL * left * get_x_prod(id << 1 | 1, m + 1, r, u, v));
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void update_X(int, int, int, int, int)':
horses.cpp:57:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   57 |   update_bit(l, 1LL * power(x[l], mod - 2) * X % mod);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:70:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  x_st[id] = min(ll(mod), 1LL * x_st[id << 1] * x_st[id << 1 | 1]);
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:103:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  return 1LL * get_bit(st[1]) * y[st[1]] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:107:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |  return 1LL * get_bit(st[1]) * y[st[1]] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:111:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |  return 1LL * get_bit(st[1]) * y[st[1]] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 43960 KB Output is correct
2 Correct 815 ms 44264 KB Output is correct
3 Correct 920 ms 44332 KB Output is correct
4 Correct 997 ms 44112 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 7 ms 33112 KB Output is correct
3 Correct 5 ms 33116 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 5 ms 33116 KB Output is correct
6 Correct 5 ms 33116 KB Output is correct
7 Correct 5 ms 33116 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 5 ms 33116 KB Output is correct
10 Correct 6 ms 33368 KB Output is correct
11 Correct 6 ms 33120 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct
13 Correct 5 ms 33120 KB Output is correct
14 Correct 5 ms 31068 KB Output is correct
15 Correct 6 ms 33116 KB Output is correct
16 Correct 6 ms 33116 KB Output is correct
17 Correct 6 ms 33116 KB Output is correct
18 Correct 6 ms 33112 KB Output is correct
19 Correct 5 ms 33116 KB Output is correct
20 Correct 5 ms 33116 KB Output is correct
21 Correct 5 ms 33116 KB Output is correct
22 Correct 5 ms 33116 KB Output is correct
23 Correct 8 ms 33116 KB Output is correct
24 Correct 8 ms 33116 KB Output is correct
25 Correct 7 ms 33116 KB Output is correct
26 Correct 7 ms 33116 KB Output is correct
27 Correct 7 ms 33128 KB Output is correct
28 Correct 7 ms 33128 KB Output is correct
29 Correct 7 ms 33116 KB Output is correct
30 Correct 7 ms 33116 KB Output is correct
31 Correct 7 ms 33116 KB Output is correct
32 Correct 9 ms 33116 KB Output is correct
33 Correct 1224 ms 43196 KB Output is correct
34 Correct 1177 ms 43344 KB Output is correct
35 Correct 598 ms 43352 KB Output is correct
36 Correct 597 ms 43192 KB Output is correct
37 Correct 917 ms 43192 KB Output is correct
38 Correct 693 ms 43488 KB Output is correct
39 Correct 900 ms 43192 KB Output is correct
40 Correct 573 ms 43092 KB Output is correct
41 Correct 906 ms 43192 KB Output is correct
42 Correct 958 ms 43404 KB Output is correct
43 Correct 563 ms 43348 KB Output is correct
44 Correct 560 ms 43196 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 6 ms 33116 KB Output is correct
3 Correct 5 ms 33104 KB Output is correct
4 Correct 5 ms 33116 KB Output is correct
5 Correct 5 ms 33112 KB Output is correct
6 Correct 5 ms 33112 KB Output is correct
7 Correct 5 ms 33112 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 6 ms 33120 KB Output is correct
10 Correct 7 ms 32920 KB Output is correct
11 Correct 5 ms 33112 KB Output is correct
12 Correct 6 ms 31064 KB Output is correct
13 Correct 6 ms 32880 KB Output is correct
14 Correct 5 ms 31068 KB Output is correct
15 Correct 5 ms 33116 KB Output is correct
16 Correct 5 ms 33116 KB Output is correct
17 Correct 5 ms 33112 KB Output is correct
18 Correct 5 ms 33112 KB Output is correct
19 Correct 5 ms 33108 KB Output is correct
20 Correct 5 ms 33116 KB Output is correct
21 Correct 6 ms 33116 KB Output is correct
22 Correct 6 ms 33132 KB Output is correct
23 Correct 9 ms 33116 KB Output is correct
24 Correct 7 ms 33104 KB Output is correct
25 Correct 7 ms 33116 KB Output is correct
26 Correct 7 ms 33116 KB Output is correct
27 Correct 7 ms 33152 KB Output is correct
28 Correct 7 ms 33112 KB Output is correct
29 Correct 7 ms 33116 KB Output is correct
30 Correct 7 ms 33116 KB Output is correct
31 Correct 7 ms 33112 KB Output is correct
32 Correct 9 ms 33148 KB Output is correct
33 Correct 768 ms 43968 KB Output is correct
34 Correct 811 ms 44108 KB Output is correct
35 Correct 931 ms 44232 KB Output is correct
36 Correct 1067 ms 44352 KB Output is correct
37 Correct 1225 ms 43192 KB Output is correct
38 Correct 1283 ms 43208 KB Output is correct
39 Correct 637 ms 43184 KB Output is correct
40 Correct 625 ms 43284 KB Output is correct
41 Correct 943 ms 43344 KB Output is correct
42 Correct 719 ms 43200 KB Output is correct
43 Correct 924 ms 43192 KB Output is correct
44 Correct 602 ms 43192 KB Output is correct
45 Correct 1069 ms 43196 KB Output is correct
46 Correct 985 ms 43196 KB Output is correct
47 Correct 613 ms 43192 KB Output is correct
48 Correct 599 ms 43448 KB Output is correct
49 Execution timed out 1558 ms 43724 KB Time limit exceeded
50 Halted 0 ms 0 KB -