oj.uz

Submission #984296

# Submission time Handle Problem Language Result Execution time Memory
984296 2024-05-16T12:50:33 Z SmuggingSpun Horses (IOI15_horses) C++14
100 / 100
 546 ms 31624 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, st[lim << 2], x[lim], x_st[lim << 1], 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 l, int r){
	int res = 1;
	for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1){
		if(l & 1){
			res = min(ll(mod), 1LL * res * x_st[l++]);
		}
		if(r & 1){
			res = min(ll(mod), 1LL * res * x_st[--r]);
		}
	}
	return res;
}
void modify_x(int p, int X){
	update_bit(p, 1LL * power(x[p], mod - 2) * X % mod);
	x[p] = X;
	for(x_st[p += n] = X; p > 1; p >>= 1){
		x_st[p >> 1] = min(ll(mod), 1LL * x_st[p] * x_st[p ^ 1]);
	}
}
int merge(int l, int r){
	if(l == 0){
		return r;
	}
	if(r == 0){
		return l;
	}
	return 1LL * get_x_prod(l + 1, r) * y[r] < ll(y[l]) ? l : r;
}
void update_X(int id, int l, int r, int p, int X){
	if(l == r){
		modify_x(st[id] = l, 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(st[id << 1], 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(st[id << 1], st[id << 1 | 1]);
	}
}
int init(int N, int X[], int Y[]){
	fill(bit, bit + lim, 1);
	fill(x_st, x_st + (lim << 1), 1);
	fill(x + 1, x + (n = N) + 1, 1);
	for(int i = 1; i <= n; i++){
		y[i] = Y[i - 1];
		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:22: note: shadowed declaration is here
   16 | int n, st[lim << 2], x[lim], x_st[lim << 1], 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)':
horses.cpp:33:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |    res = min(ll(mod), 1LL * res * x_st[l++]);
      |          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:36:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   36 |    res = min(ll(mod), 1LL * res * x_st[--r]);
      |          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void modify_x(int, int)':
horses.cpp:42:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  update_bit(p, 1LL * power(x[p], mod - 2) * X % mod);
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:45:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |   x_st[p >> 1] = min(ll(mod), 1LL * x_st[p] * x_st[p ^ 1]);
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |  return 1LL * get_bit(st[1]) * y[st[1]] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:101:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |  return 1LL * get_bit(st[1]) * y[st[1]] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:105:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  105 |  return 1LL * get_bit(st[1]) * y[st[1]] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 21968 KB Output is correct
2 Correct 546 ms 26488 KB Output is correct
3 Correct 520 ms 21772 KB Output is correct
4 Correct 517 ms 23792 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10680 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10688 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10880 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 3 ms 10840 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10840 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 11044 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 4 ms 10700 KB Output is correct
24 Correct 4 ms 10844 KB Output is correct
25 Correct 4 ms 10696 KB Output is correct
26 Correct 4 ms 10844 KB Output is correct
27 Correct 3 ms 10888 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct
29 Correct 3 ms 10844 KB Output is correct
30 Correct 3 ms 10844 KB Output is correct
31 Correct 3 ms 10892 KB Output is correct
32 Correct 3 ms 10896 KB Output is correct
33 Correct 305 ms 21428 KB Output is correct
34 Correct 296 ms 21192 KB Output is correct
35 Correct 410 ms 24404 KB Output is correct
36 Correct 434 ms 24660 KB Output is correct
37 Correct 383 ms 20312 KB Output is correct
38 Correct 352 ms 20560 KB Output is correct
39 Correct 380 ms 20164 KB Output is correct
40 Correct 392 ms 22160 KB Output is correct
41 Correct 376 ms 20168 KB Output is correct
42 Correct 374 ms 20168 KB Output is correct
43 Correct 382 ms 22048 KB Output is correct
44 Correct 388 ms 22236 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10872 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10680 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10884 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10840 KB Output is correct
18 Correct 2 ms 10840 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 3 ms 10696 KB Output is correct
25 Correct 3 ms 10844 KB Output is correct
26 Correct 3 ms 10924 KB Output is correct
27 Correct 3 ms 10844 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct
29 Correct 3 ms 10844 KB Output is correct
30 Correct 4 ms 10844 KB Output is correct
31 Correct 3 ms 10844 KB Output is correct
32 Correct 3 ms 10840 KB Output is correct
33 Correct 432 ms 21920 KB Output is correct
34 Correct 546 ms 26328 KB Output is correct
35 Correct 523 ms 21900 KB Output is correct
36 Correct 531 ms 24304 KB Output is correct
37 Correct 305 ms 21072 KB Output is correct
38 Correct 296 ms 21160 KB Output is correct
39 Correct 407 ms 24524 KB Output is correct
40 Correct 409 ms 24524 KB Output is correct
41 Correct 386 ms 20048 KB Output is correct
42 Correct 369 ms 20824 KB Output is correct
43 Correct 376 ms 20048 KB Output is correct
44 Correct 396 ms 22312 KB Output is correct
45 Correct 381 ms 20304 KB Output is correct
46 Correct 376 ms 20048 KB Output is correct
47 Correct 385 ms 22220 KB Output is correct
48 Correct 386 ms 22220 KB Output is correct
49 Correct 444 ms 22872 KB Output is correct
50 Correct 438 ms 24760 KB Output is correct
51 Correct 477 ms 31624 KB Output is correct
52 Correct 476 ms 31212 KB Output is correct
53 Correct 513 ms 23380 KB Output is correct
54 Correct 442 ms 23736 KB Output is correct
55 Correct 458 ms 21804 KB Output is correct
56 Correct 478 ms 26684 KB Output is correct
57 Correct 437 ms 22612 KB Output is correct
58 Correct 437 ms 23100 KB Output is correct
59 Correct 397 ms 25260 KB Output is correct