| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 927972 |
2024-02-15T15:31:15 Z |
pan |
Horses (IOI15_horses) |
C++17 |
|
265 ms |
107008 KB |
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll const mod = 1e9+7;
ll n;
vector<ll> x, y;
ll pow(ll n, ll k){
n %= mod;
ll res = 1;
while(k > 0){
if(k % 2) res = res * n % mod;
k /= 2;
n = n * n % mod;
}
return res;
}
ll inv(ll x){
return pow(x, mod - 2);
}
struct node{
int s, e, m; //range is [s,e], m is the middle point
ll val, logval;
ll lazy;
ld loglazy; //lazy tag of [s,e]
node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e]
node (int S, int E){ //constructor called node
s = S, e = E, m = (s+e)/2;
val = 1; logval = 0; //initially all values are 0
lazy = 1; loglazy = (ld) 0.0; //lazy tag of 0 will mean there is no update (sentinel value)
if(s != e){ //node is not yet a leaf, so create two children
l = new node(s, m); //create left child
r = new node(m+1, e); //create right child
}
}
void propogate(){
if (lazy==1 && loglazy == 0) return; //nothing happens
val = (val*lazy)%mod;//(e-s+1) is the length of the range
logval+=loglazy;
if (s != e){ //not a leaf, send lazy tags to children
l->lazy = (l->lazy*lazy)%mod;
r->lazy = (r->lazy*lazy)%mod;
l->loglazy+=loglazy;
r->loglazy+=loglazy;
}
lazy=1; //set our lazy tag value back to the sentinel
loglazy = 0.0;
}
void update(int S, int E, ll V, ld logv){ //increment [S,E] by V
propogate();
if(s==S && e==E)//update covers range, update lazy tag
{
lazy = (lazy*(V))%mod;
loglazy += logv;
}
else{ //go we have to go deeper
if(E <= m) l->update(S, E, V, logv); //[S,E] is in the left child
else if (m < S) r->update(S, E, V, logv); //[S,E] is in the right child
else l->update(S, m, V, logv),r->update(m+1, E, V, logv);
l->propogate(),r->propogate();
//remember to propogate your children before update yourself
if (l-> logval>r->logval)
{
logval = l-> logval;
val = l-> val;
}
else
{
logval = r->logval;
val = r->val;
}
}
}
} *root;
int init(int N, int X[], int Y[])
{
root = new node(0, N);
n=N;
x.resize(n); y.resize(n);
for (ll i=0; i<n; ++i) x[i] = X[i];
for (ll i=0; i<n; ++i) y[i] = Y[i];
ll val = 1;
ld logval = 0.0;
for (ll i=0; i<n; ++i)
{
val = (val*X[i])%mod;
logval+=logl(X[i]);
root->update(i, i, val*(Y[i]%mod)%mod, logval + logl(Y[i]));
}
root->propogate();
return root-> val;
}
int updateX(int pos, int val)
{
root->update(pos, n-1, (inv(x[pos])*(val%mod))%mod, logl(val)-logl(x[pos]));
x[pos] = val;
root->propogate();
return root->val;
}
int updateY(int pos, int val)
{
root->update(pos, pos, (inv(y[pos])*(val%mod))%mod, logl(val)-logl(y[pos]));
y[pos]= val;
root->propogate();
return root->val;
}
Compilation message
horses.cpp: In function 'll pow(ll, ll)':
horses.cpp:33:11: warning: declaration of 'n' shadows a global declaration [-Wshadow]
33 | ll pow(ll n, ll k){
| ~~~^
horses.cpp:31:4: note: shadowed declaration is here
31 | ll n;
| ^
horses.cpp: In function 'll inv(ll)':
horses.cpp:44:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
44 | ll inv(ll x){
| ~~~^
horses.cpp:32:12: note: shadowed declaration is here
32 | vector<ll> x, y;
| ^
horses.cpp: In member function 'void node::propogate()':
horses.cpp:67:14: warning: conversion from 'ld' {aka 'long double'} to 'll' {aka 'long long int'} may change value [-Wfloat-conversion]
67 | logval+=loglazy;
| ~~~~~~^~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:120:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
120 | root->update(i, i, val*(Y[i]%mod)%mod, logval + logl(Y[i]));
| ^
horses.cpp:120:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
120 | root->update(i, i, val*(Y[i]%mod)%mod, logval + logl(Y[i]));
| ^
horses.cpp:123:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
123 | return root-> val;
| ~~~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:128:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
128 | root->update(pos, n-1, (inv(x[pos])*(val%mod))%mod, logl(val)-logl(x[pos]));
| ~^~
horses.cpp:131:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
131 | return root->val;
| ~~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
138 | return root->val;
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
265 ms |
107008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
