| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 735798 |
2023-05-04T16:47:06 Z |
snowman |
Horses (IOI15_horses) |
C++17 |
|
70 ms |
45820 KB |
#include <bits/stdc++.h>
#include "horses.h"
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
// #define Y cout << "YES" << '\n'
// #define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}
const ll mxa = 500005;
// string __fname = "exclusiv";
// ifstream in(__fname + ".in");
// ofstream out (__fname + ".out");
// #define cin in
// #define cout out
struct cell{
double lsum, blsum;
ll prod, bprod;
};
int n;
ll x[mxa], y[mxa];
cell st[4 * mxa];
void combine(int v, int l, int r){
st[v].lsum = st[l].lsum + st[r].lsum;
st[v].prod = (st[l].prod + st[r].prod) % mod;
if(st[l].blsum > st[l].lsum + st[r].blsum){
st[v].blsum = st[l].blsum;
st[v].bprod = st[l].bprod;
}
else{
st[v].blsum = st[l].lsum + st[r].blsum;
st[v].bprod = (st[l].prod * st[r].bprod) % mod;
}
}
void build(int v, int tl, int tr){
if(tl == tr){
st[v].lsum = log2(x[tl]);
st[v].prod = x[tl];
st[v].blsum = st[v].lsum + log2(y[tl]);
st[v].bprod = (st[v].prod * y[tl]) % mod;
}
else{
int mid = (tl + tr) / 2;
build(v*2, tl, mid);
build(v * 2 + 1, mid + 1, tr);
combine(v, v * 2, v * 2 + 1);
}
}
void update(int v, int tl, int tr, int poz){
if(tl == tr && tl == poz){
st[v].lsum = log2(x[tl]);
st[v].prod = x[tl];
st[v].blsum = st[v].lsum + log2(y[tl]);
st[v].bprod = (st[v].prod * y[tl]) % mod;
}
else{
int mid = (tl + tr) / 2;
if(poz <= mid){
update(v * 2, tl, mid, poz);
}
else{
update(v * 2 + 1, mid + 1, tr, poz);
}
combine(v, v * 2, v * 2 + 1);
}
}
int init(int N, int X[], int Y[]) {
n = N;
fri(0, n){
x[i] = X[i];
y[i] = Y[i];
}
build(1, 0, n - 1);
return st[1].bprod;
}
int updateX(int pos, int val) {
x[pos] = val;
update(1, 0, n - 1, pos);
return st[1].bprod;
}
int updateY(int pos, int val) {
y[pos] = val;
update(1, 0, n - 1, pos);
return st[1].bprod;
}
Compilation message
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:109:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
109 | return st[1].bprod;
| ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
115 | return st[1].bprod;
| ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:121:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
121 | return st[1].bprod;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
45820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
