| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 920931 |
2024-02-03T08:05:03 Z |
oblantis |
Horses (IOI15_horses) |
C++17 |
|
390 ms |
46612 KB |
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 5e5 + 1;
#include "horses.h"
int t[maxn * 4], it, nw, n, xl, xr;
int a[maxn], b[maxn], mx[maxn * 4];
set<int> s;
void upd(int v, int l, int r){
if(l + 1 == r){
t[v] = a[l];
mx[v] = b[l];
return;
}
if((l + r) / 2 <= it)upd(v * 2 + 2, (l + r) / 2, r);
else upd(v * 2 + 1, l, (l + r) / 2);
t[v] = 1ll * t[v * 2 + 1] * t[v * 2 + 2] % mod;
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int gm(int v, int l, int r){
if(xl <= l)return mx[v];
if(r <= xl)return 0;
return max(gm(v * 2 + 1, l, (l + r) / 2), gm(v * 2 + 2, (l + r) / 2, r));
}
int mlp(int v, int l, int r){
if(r <= xl + 1)return t[v];
if(xl < l) return 1;
return 1ll * mlp(v * 2 + 1, l, (l + r) / 2) * mlp(v * 2 + 2, (l + r) / 2, r) % mod;
}
int get(){
int ans = 1, p = 1;
if(s.empty()){
xl = 0;
return gm(0, 0, n);
}
auto i = --s.end();
while(1){
xl = *i;
int nx = gm(0, 0, n);
if(p <= nx){
ans = 1ll * nx * mlp(0, 0, n) % mod;
}
if(1ll * p * a[xl] > inf)break;
p *= a[xl];
if(i == s.begin())break;
--i;
}
return ans;
}
int init(int M, int x[], int y[]) {
n = M;
for(int i = 0; i < n; i++){
a[i] = x[i], b[i] = y[i];
it = i;
upd(0, 0, n);
if(a[i] != 1)s.insert(i);
}
return get();
}
int updateX(int pos, int val) {
if(a[pos] == val)return get();
if(a[pos] == 1)s.insert(pos);
else if(val == 1)s.erase(pos);
it = pos;
a[it] = val;
upd(0, 0, n);
return get();
}
int updateY(int pos, int val) {
it = pos;
b[it] = val;
upd(0, 0, n);
return get();
}
//void solve() {
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
//3
//2 1 3
//3 4 1
//1
//2 1 2
//0
//0
//int main() {
//int N;
//cin >> N;
//int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
//int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);
//for (int i = 0; i < N; i++) {
//cin >> X[i];
//}
//for (int i = 0; i < N; i++) {
//cin >> Y[i];
//}
//int M;
//cin >> M;
//for (int i = 0; i < M; i++) {
//int type; cin >> type;
//int pos; cin >> pos;
//int val; cin >> val;
//if (type == 1) {
//cout << updateX(pos,val) << '\n';
//} else if (type == 2) {
//cout << updateY(pos,val) << '\n';
//}
//}
//return 0;
//}
Compilation message
horses.cpp: In function 'void upd(int, int, int)':
horses.cpp:31:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
31 | t[v] = 1ll * t[v * 2 + 1] * t[v * 2 + 2] % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int mlp(int, int, int)':
horses.cpp:42:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
42 | return 1ll * mlp(v * 2 + 1, l, (l + r) / 2) * mlp(v * 2 + 2, (l + r) / 2, r) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get()':
horses.cpp:55:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
55 | ans = 1ll * nx * mlp(0, 0, n) % mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
46612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
