Submission #1039454

#TimeUsernameProblemLanguageResultExecution timeMemory
1039454HappyCapybaraHorses (IOI15_horses)C++17
0 / 100
1578 ms73044 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define ll long long int n; vector<pair<int,double>> stl; vector<double> lazy; vector<ll> stm; vector<int> x, y; void updatem(int pos, int val, int node=1, int tl=0, int tr=n-1){ if (tl == tr){ stm[node] = val; return; } int tm = (tl+tr)/2; if (pos <= tm) updatem(pos, val, node*2, tl, tm); else updatem(pos, val, node*2+1, tm+1, tr); stm[node] = (stm[node*2]*stm[node*2+1]) % 1000000007; } int querym(int l, int r, int node=1, int tl=0, int tr=n-1){ //cout << l << " " << r << " " << tl << " " << tr << "\n"; if (l <= tl && tr <= r) return stm[node]; int tm = (tl+tr)/2; int res = 1; if (l <= tm) res = (res*querym(l, r, node*2, tl, tm)) % 1000000007; if (tm+1 <= r) res = (res*querym(l, r, node*2+1, tm+1, tr)) % 1000000007; return res; } void prop(int node, int tl, int tr){ stl[node].second += lazy[node]; if (tl != tr){ lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } lazy[node] = 0; } pair<int,double> merge(int a, int b){ if (stl[a].second > stl[b].second) return stl[a]; return stl[b]; } void updatel(int l, int r, double val, int node=1, int tl=0, int tr=n-1){ if (l <= tl && tr <= r){ lazy[node] += val; prop(node, tl, tr); return; } prop(node, tl, tr); int tm = (tl+tr)/2; if (l <= tm) updatel(l, r, val, node*2, tl, tm); if (tm+1 <= r) updatel(l, r, val, node*2+1, tm+1, tr); stl[node] = merge(node*2, node*2+1); } void updatelp(int pos, double val, int node=1, int tl=0, int tr=n-1){ prop(node, tl, tr); if (tl == tr){ stl[node].first = pos; stl[node].second += val; return; } int tm = (tl+tr)/2; if (pos <= tm) updatelp(pos, val, node*2, tl, tm); else updatelp(pos, val, node*2+1, tm+1, tr); stl[node] = merge(node*2, node*2+1); } int init(int N, int X[], int Y[]){ n = N; stl.resize(4*N, {-1, 0}); lazy.resize(4*N, 0); stm.resize(4*N, 1); x.resize(N); y.resize(N); for (int i=0; i<N; i++){ y[i] = Y[i]; x[i] = X[i]; updatem(i, X[i]); updatelp(i, Y[i]); updatel(i, N-1, log(X[i])); /*for (int j=1; j<4*N; j++){ cout << stl[j].first << " " << stl[j].second << " | "; if ((j+1) == pow(2, floor(log2(j+1)))) cout << "\n"; } cout << "\n\n";*/ } double curd = 0, bsfd = 0; ll cur = 1, bsf = 0; for (int i=0; i<N; i++){ curd += log(x[i]); cur = (cur*x[i]) % 1000000007; if (curd+log(Y[i]) > bsfd){ bsfd = curd+log(Y[i]); bsf = (cur*y[i]) % 1000000007; } } return bsf; return querym(0, stl[1].first)*y[stl[1].first] % 1000000007; } int updateX(int pos, int val){ updatel(pos, n-1, log(val)-log(x[pos])); x[pos] = val; double curd = 0, bsfd = 0; ll cur = 1, bsf = 0; for (int i=0; i<n; i++){ curd += log(x[i]); cur = (cur*x[i]) % 1000000007; if (curd+log(y[i]) > bsfd){ bsfd = curd+log(y[i]); bsf = (cur*y[i]) % 1000000007; } } return bsf; return querym(0, stl[1].first)*y[stl[1].first] % 1000000007; } int updateY(int pos, int val){ updatelp(pos, val-y[pos]); y[pos] = val; double curd = 0, bsfd = 0; ll cur = 1, bsf = 0; for (int i=0; i<n; i++){ curd += log(x[i]); cur = (cur*x[i]) % 1000000007; if (curd+log(y[i]) > bsfd){ bsfd = curd+log(y[i]); bsf = (cur*y[i]) % 1000000007; } } return bsf; return querym(0, stl[1].first)*y[stl[1].first] % 1000000007; }

Compilation message (stderr)

horses.cpp: In function 'int querym(int, int, int, int, int)':
horses.cpp:26:41: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |  if (l <= tl && tr <= r) return stm[node];
      |                                         ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:104:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |  return bsf;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  return bsf;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:142:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  142 |  return bsf;
      |         ^~~
#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...