| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 964460 | beaboss | 말 (IOI15_horses) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Source: https://oj.uz/problem/view/IOI15_horses
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
const ll N = 1e5 + 10;
const ll MOD = 1e9 + 7;
#define lc i << 1
#define rc (i << 1) + 1
ll binpow(ll x, ll n) { // x ^ n
ll res = 1;
while (n > 0) {
if (n & 1) res = (res * x) % MOD;
x = (x * x) % MOD;
n/=2;
}
return res;
}
struct node {
ll val, lz;
} st[4 * N];
void down(ll i) {
if (st[i].lz == 1) return;
st[lc].lz = st[lc].lz * st[i].lz % MOD;
st[rc].lz = st[rc].lz * st[i].lz %MOD;
st[lc].val = st[lc].val * st[i].lz % MOD;
st[rc].val = st[rc].val * st[i].lz % MOD;
st[i].lz = 1;
}
void up(ll i) {
st[i].val = max(st[lc].val, st[rc].val);
}
void update(ll ul, ll ur, ll val, ll i = 1, ll l = 0, ll r = N) {
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
if (r == l) return;
if (ul <= l && r <= ur) {
st[i].lz = (st[i].lz*val) % MOD;
st[i].val = (st[i].val * val) % MOD;
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
return;
}
if (l == r-1) return;
down(i);
ll m = (l + r) / 2;
if (ul < m) update(ul, ur, val, lc, l, m);
if (m < ur) update(ul, ur, val, rc, m, r);
up(i);
// cout << l << r << ' ' << st[i].lz << ' ' << val << endl;
}
vi fx, fy;
ll nn;
ll init(int n, vector<int> x, vector<int> y) {
nn = n;
fx = x, fy = y;
FOR(i, 0, 4 * N) {
st[i].val = st[i].lz = 1;
}
FOR(i, 0, n) {
update(i, n, x[i]);
// break;
update(i, i + 1, y[i]);
// break;
}
return st[1].val;
}
ll updateX(int pos, int val) {
update(pos, nn, binpow(fx[pos], MOD-2));
fx[pos]=val;
update(pos, nn, fx[pos]);
return st[1].val;
}
ll updateY(int pos, int val) {
update(pos, pos + 1, binpow(fy[pos], MOD-2));
fy[pos]=val;
update(pos, pos, fy[pos]);
return st[1].val;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << init(3, {2, 1, 3}, {3, 4, 1}) << endl;
// cout << updateY(1, 2) << endl;
// }