| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 597154 |
2022-07-15T15:48:51 Z |
Apiram |
Horses (IOI15_horses) |
C++14 |
|
480 ms |
52400 KB |
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct dataa2{
long long ans = 0,v = 0,index = 0;
void add(long long val){
v = val;
}
};
struct dataa{
long long v = 0;
bool ok = 1;
void add(long long val){
v = val;
//sum += val *(right - left + 1);
}
};
struct Segment_Tree{
vector<dataa>tree;
void build(long long node,long long left,long long right,vector<long long>&arr,long long n){
if (left == right){
tree[node].v = arr[left];
return ;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
build(node + 1,left,mid,arr,n);
build(z,mid + 1,right,arr,n);
tree[node] = combine(tree[node + 1],tree[z]);
}
void init(long long n,vector<long long>&arr){
tree.resize(2*n - 1);
build(0,0,n-1,arr,n);
}
dataa combine(dataa left,dataa right){
dataa res;
res.v = (left.v * right.v)%mod;
res.ok = left.ok & right.ok;
if (res.ok){
if (left.v * right.v > 1e9)res.ok = false;
}
return res;
}
dataa query(long long node,long long left,long long right,long long qleft,long long qright){
if (qright<left|| qleft > right)return {1,1};
if (qleft<=left && qright>=right){
return tree[node];
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
}
void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
if (left > uright || right < uleft) return;
if (uleft <= left && right <=uright){
tree[node].add(v);
return;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (uleft<=mid){
update(node + 1,left,mid,uleft,uright,v);
}
if (uright > mid){
update(z,mid + 1,right,uleft,uright,v);
}
tree[node] = combine(tree[node + 1],tree[z]);
}
};
Segment_Tree st;
struct Segment_Tree2{
vector<dataa2>tree;
int N;
void build(long long node,long long left,long long right,vector<long long>&arr,long long n){
if (left == right){
tree[node].v = arr[left];
tree[node].ans = (arr[left] * st.query(0,0,n - 1,0,left).v)%mod;
tree[node].index = left;
return ;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
build(node + 1,left,mid,arr,n);
build(z,mid + 1,right,arr,n);
tree[node] = combine(tree[node + 1],tree[z]);
}
void init(long long n,vector<long long>&arr){
tree.resize(2*n - 1);
N = n;
build(0,0,n-1,arr,n);
}
dataa2 combine(dataa2 left,dataa2 right){
dataa2 res;
auto temp = st.query(0,0,N - 1,left.index + 1,right.index);
bool ok = temp.ok;
if (left.v > right.v && (ok && temp.v * left.v <= right.v)){
res.v = left.v;
res.index = left.index;
temp = st.query(0,0,N - 1,0,left.index);
res.ans = (temp.v * left.v)%mod;
}
else{
res.v = right.v;
res.index = right.index;
temp = st.query(0,0,N - 1,0,right.index);
res.ans = (temp.v * right.v)%mod;
}
return res;
}
dataa2 query(long long node,long long left,long long right,long long qleft,long long qright){
if (qright<left|| qleft > right)return {0,0,0};
if (qleft<=left && qright>=right){
return tree[node];
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
}
void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
if (left > uright || right < uleft) return;
if (uleft <= left && right <=uright){
tree[node].add(v);
return;
}
long long mid = (left + right)>>1;
long long z = node + ((mid - left + 1)<<1);
if (uleft<=mid){
update(node + 1,left,mid,uleft,uright,v);
}
if (uright > mid){
update(z,mid + 1,right,uleft,uright,v);
}
tree[node] = combine(tree[node + 1],tree[z]);
}
};
vector<long long>x,y;
Segment_Tree2 st2;
int solve(){
int N = (int)x.size();
return st2.query(0,0,N - 1,0,N - 1).ans;
}
int init(int N, int X[], int Y[]) {
for (int i = 0;i<N;++i){
x.push_back(X[i]);
y.push_back(Y[i]);
}
st.init(N,x);
st2.init(N,y);
return solve();
}
int updateX(int pos, int val) {
st.update(0,0,(int)x.size()-1,pos,pos,val);
st2.update(0,0,(int)x.size() - 1,pos,pos,y[pos]);
return solve();
}
int updateY(int pos, int val) {
y[pos] = val;
st2.update(0,0,(int)x.size() - 1,pos,pos,y[pos]);
return solve();
}
Compilation message
horses.cpp: In member function 'dataa Segment_Tree::combine(dataa, dataa)':
horses.cpp:41:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
41 | if (left.v * right.v > 1e9)res.ok = false;
| ~~~~~~~^~~~~~~~~
horses.cpp: In member function 'void Segment_Tree2::init(long long int, std::vector<long long int>&)':
horses.cpp:90:7: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
90 | N = n;
| ^
horses.cpp: In function 'int solve()':
horses.cpp:141:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
141 | return st2.query(0,0,N - 1,0,N - 1).ans;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
480 ms |
52400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
