Submission #133598

#TimeUsernameProblemLanguageResultExecution timeMemory
133598Mahdi_JfriHorses (IOI15_horses)C++14
37 / 100
1138 ms19704 KiB
#include "horses.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 5e5 + 20; const int mod = 1e9 + 7; int maxy[maxn * 4] , mulx[maxn * 4] , t[maxn * 4] , n; int x[maxn]; void updx(int p , int val , int s = 0 , int e = n , int v = 1) { if(e - s < 2) { mulx[v] = val; t[v] = val > 1; return; } int m = (s + e) / 2; if(p < m) updx(p , val , s , m , 2 * v); else updx(p , val , m , e , 2 * v + 1); mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod; t[v] = t[2 * v] + t[2 * v + 1]; } void updy(int p , int val , int s = 0 , int e = n , int v = 1) { if(e - s < 2) { maxy[v] = val; return; } int m = (s + e) / 2; if(p < m) updy(p , val , s , m , 2 * v); else updy(p , val , m , e , 2 * v + 1); maxy[v] = max(maxy[2 * v] , maxy[2 * v + 1]); } int getx(int l , int r , int s = 0 , int e = n , int v = 1) { if(l <= s && e <= r) return mulx[v]; else if(r <= s || e <= l) return 1; int m = (s + e) / 2; return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod; } int gety(int l , int r , int s = 0 , int e = n , int v = 1) { if(l <= s && e <= r) return maxy[v]; if(r <= s || e <= l) return 0; int m = (s + e) / 2; return max(gety(l , r , s , m , 2 * v) , gety(l , r , m , e , 2 * v + 1)); } void ux(int p , int val) { x[p] = val; updx(p , val); } vector<int> tmp; void get(int k = 35 , int s = 0 , int e = n , int v = 1) { if(k <= 0 || !t[v]) return; if(e - s < 2) { tmp.pb(s); return; } int m = (s + e) / 2; get(k , m , e , 2 * v + 1); k -= t[2 * v + 1]; get(k , s , m , 2 * v); } int solve() { tmp.clear(); get(); if(tmp.empty()) return gety(0 , n); reverse(tmp.begin() , tmp.end()); int m = tmp.size(); tmp.pb(n); vector<int> y; for(int i = 0; i < m; i++) y.pb(gety(tmp[i] , tmp[i + 1])); for(int i = 0; i < m; i++) { bool good = 1; ll mul = 1; for(int j = i + 1; j < m && good; j++) { mul = min((ll)2e9 , 1LL * mul * x[tmp[j]]); if(y[i] <= mul * y[j]) good = 0; } if(good) return 1LL * getx(0 , tmp[i] + 1) * y[i] % mod; } return -1; } int init(int N, int X[], int Y[]) { n = N; for(int i = 0; i < n; i++) { ux(i , X[i]); updy(i , Y[i]); } return solve(); } int updateX(int pos, int val) { ux(pos , val); return solve(); } int updateY(int pos, int val) { updy(pos , val); return solve(); }

Compilation message (stderr)

horses.cpp: In function 'void updx(int, int, int, int, int)':
horses.cpp:31:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  mulx[v] = 1LL * mulx[2 * v] * mulx[2 * v + 1] % mod;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getx(int, int, int, int, int)':
horses.cpp:61:77: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * getx(l , r , s , m , 2 * v) * getx(l , r , m , e , 2 * v + 1) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:108:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int m = tmp.size();
          ~~~~~~~~^~
horses.cpp:128:45: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    return 1LL * getx(0 , tmp[i] + 1) * y[i] % 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...