Submission #1026893

#TimeUsernameProblemLanguageResultExecution timeMemory
1026893TraianDanciuHorses (IOI15_horses)C++17
54 / 100
798 ms71808 KiB
#include "horses.h" #include <math.h> #define MAXN 500000 #define MOD 1000000007 void euclid(long long a, long long b, long long &x, long long &y) { long long x0, y0; if(b == 0) { x = 1; y = 0; } else { euclid(b, a % b, x0, y0); x = y0; y = x0 - a / b * y0; } } struct Numar { double ln; int val; Numar(int _val) { val = _val % MOD; ln = log(val); } Numar() {} inline Numar operator *(Numar oth) { Numar ret; ret.val = 1LL * val * oth.val % MOD; ret.ln = ln + oth.ln; return ret; } inline Numar operator /(Numar oth) { Numar ret; long long x, y; euclid(oth.val, MOD, x, y); x %= MOD; if(x < 0) { x += MOD; } ret.val = 1LL * val * x % MOD; ret.ln = ln - oth.ln; return ret; } inline bool operator <(Numar oth) { return ln < oth.ln; } }; static inline Numar max(Numar a, Numar b) { return a < b ? b : a; } Numar aint[4 * MAXN], lazy[4 * MAXN], qval; int n, x[MAXN], y[MAXN], qleft, qright; void propagate(int node, int left, int right) { aint[node] = aint[node] * lazy[node]; if(left < right) { lazy[2 * node + 1] = lazy[2 * node + 1] * lazy[node]; lazy[2 * node + 2] = lazy[2 * node + 2] * lazy[node]; } lazy[node] = Numar(1); } void _update(int node, int left, int right) { int middle; propagate(node, left, right); if(qleft <= left && right <= qright) { lazy[node] = lazy[node] * qval; propagate(node, left, right); } else { middle = (left + right) / 2; propagate(2 * node + 1, left, middle); propagate(2 * node + 2, middle + 1, right); if(qleft <= middle) { _update(2 * node + 1, left, middle); } if(middle < qright) { _update(2 * node + 2, middle + 1, right); } aint[node] = max(aint[2 * node + 1], aint[2 * node + 2]); } } void update(int _qleft, int _qright, Numar _qval) { qleft = _qleft; qright = _qright; qval = _qval; _update(0, 0, n - 1); } Numar _query(int node, int left, int right) { int middle; Numar ans; propagate(node, left, right); if(qleft <= left && right <= qright) { return aint[node]; } middle = (left + right) / 2; if(qleft <= middle && middle < qright) { ans = max(_query(2 * node + 1, left, middle), _query(2 * node + 2, middle + 1, right)); } else if(qleft <= middle) { ans = _query(2 * node + 1, left, middle); } else { ans = _query(2 * node + 2, middle + 1, right); } return ans; } Numar query(int _qleft, int _qright) { qleft = _qleft; qright = _qright; return _query(0, 0, n - 1); } int init(int _n, int _x[], int _y[]) { int i; n = _n; for(i = 0; i < 4 * n; i++) { aint[i] = lazy[i] = Numar(1); } for(i = 0; i < n; i++) { x[i] = _x[i]; update(i, n - 1, Numar(x[i])); y[i] = _y[i]; update(i, i, Numar(y[i])); } return query(0, n - 1).val; } int updateX(int pos, int val) { update(pos, n - 1, Numar(val) / Numar(x[pos])); x[pos] = val; return query(0, n - 1).val; } int updateY(int pos, int val) { update(pos, pos, Numar(val) / Numar(y[pos])); y[pos] = val; return query(0, n - 1).val; }

Compilation message (stderr)

horses.cpp: In member function 'Numar Numar::operator*(Numar)':
horses.cpp:33:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |     ret.val = 1LL * val * oth.val % MOD;
      |                                   ^
horses.cpp: In member function 'Numar Numar::operator/(Numar)':
horses.cpp:46:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |     ret.val = 1LL * val * x % 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...