제출 #206565

#제출 시각아이디문제언어결과실행 시간메모리
206565spdskatr말 (IOI15_horses)C++14
17 / 100
219 ms40952 KiB
#include "horses.h" #include <cassert> #include <cstdio> #include <cstdlib> #include <vector> #include <utility> #define MOD 1000000007 #define SZ (1<<19) using namespace std; typedef long long ll; ll mulst[1<<20], ansst[1<<20]; int x[1<<19], y[1<<19]; // Segtree stores best year to sell horses in range int st[1<<20]; ll mulover(ll a, ll b) { if (a == -1 || b == -1) return -1; if (a * b > 1000000000) return -1; return a*b; } ll prod(int l, int r) { ll res = 1; for (l += SZ, r += SZ; res != -1 && l < r; l >>= 1, r >>= 1) { if (l&1) res = mulover(res, mulst[l++]); if (r&1) res = mulover(res, mulst[--r]); } return res; } ll prodans(int l, int r) { ll res = 1; for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) { if (l&1) res = (res * ansst[l++]) % MOD; if (r&1) res = (res * ansst[--r]) % MOD; } return res; } int stc(int i, int j) { if (j > 1000000000) return i; //printf("stc(%d, %d)\n", i, j); assert(i <= j); ll val = mulover(prod(i+1, j+1), y[j]); if (val == -1 || val > y[i]) { return j; } return i; } int init(int N, int X[], int Y[]) { for (int i = 0; i < N; i++) { x[i] = X[i]; y[i] = Y[i]; mulst[i+SZ] = ansst[i+SZ] = x[i]; st[i+SZ] = i; } for (int i = N; i < SZ; i++) { st[i+SZ] = 2069696969; } for (int i = SZ-1; i > 0; i--) { mulst[i] = mulover(mulst[i<<1], mulst[i<<1|1]); ansst[i] = (ansst[i<<1] * ansst[i<<1|1]) % MOD; } for (int i = SZ-1; i > 0; i--) { st[i] = stc(st[i<<1], st[i<<1|1]); } //printf("Optimal position: %d\n", st[1]); return (int)((prodans(0, st[1]+1) * y[st[1]]) % MOD); } int updateX(int pos, int val) { x[pos] = val; int i = pos + SZ; mulst[i] = val; i >>= 1; for (; i > 0; i >>= 1) st[i] = stc(st[i<<1], st[i<<1|1]); //printf("Optimal position: %d\n", st[1]); return (int)((prodans(0, st[1]+1) * y[st[1]]) % MOD); } int updateY(int pos, int val) { y[pos] = val; int i = pos + SZ; i >>= 1; for (; i > 0; i >>= 1) st[i] = stc(st[i<<1], st[i<<1|1]); //printf("Optimal position: %d\n", st[1]); return (int)((prodans(0, st[1]+1) * y[st[1]]) % MOD); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...