Submission #819917

#TimeUsernameProblemLanguageResultExecution timeMemory
819917KerimHorses (IOI15_horses)C++17
34 / 100
1562 ms31348 KiB
#include "horses.h" #include "bits/stdc++.h" #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #define ff first #define ss second using namespace std; typedef pair<int,int> pii; const int MAXN = 5e5+5; const int INF = 1e9+7; int a[MAXN], b[MAXN], n; pii s[MAXN<<2]; int ans[MAXN<<2]; pii merge(pii x, pii y){ pii z; z.ff = min(x.ff * 1LL * y.ff, INF * 1LL); z.ss = (x.ss * 1LL * y.ss) % INF; return z; } pii get(int l, int r, int nd, int x, int y){ if (l > y or x > r) return {1, 1}; if (l <= x and y <= r) return s[nd]; int mid = (x+y) >> 1; return merge(get(l, r, nd<<1, x, mid), get(l, r, nd<<1|1, mid+1, y)); } int cmp(int x, int y){ if (x == y) return 0; if (x > y) swap(x, y); return b[x] < b[y] * 1LL * get(x+1, y, 1, 0, n-1).ff; } void upd(int p, int nd, int x, int y){ if (x == y){ ans[nd] = x; s[nd].ff = s[nd].ss = a[p]; return; } int mid = (x+y) >> 1; if (p <= mid) upd(p, nd<<1, x, mid); else upd(p, nd<<1|1, mid+1, y); s[nd] = merge(s[nd<<1], s[nd<<1|1]); if (cmp(ans[nd<<1], ans[nd<<1|1])) ans[nd] = ans[nd<<1|1]; else ans[nd] = ans[nd<<1]; } int ask(int pos){ return (get(0, pos, 1, 0, n-1).ss *1LL* b[pos]) % INF; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++){ a[i] = X[i], b[i] = Y[i]; upd(i, 1, 0, n-1); } return ask(ans[1]); } int updateX(int pos, int val) { a[pos] = val; upd(pos, 1, 0, n-1); return ask(ans[1]); } int updateY(int pos, int val) { b[pos] = val; upd(pos, 1, 0, n-1); return ask(ans[1]); }

Compilation message (stderr)

horses.cpp: In function 'pii merge(pii, pii)':
horses.cpp:21:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |  z.ff = min(x.ff * 1LL * y.ff, INF * 1LL);
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:22:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |  z.ss = (x.ss * 1LL * y.ss) % INF;
      |         ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ask(int)':
horses.cpp:63:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |  return (get(0, pos, 1, 0, n-1).ss *1LL* b[pos]) % INF;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#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...