Submission #285890

#TimeUsernameProblemLanguageResultExecution timeMemory
285890Atill83말 (IOI15_horses)C++14
77 / 100
1567 ms73080 KiB
#include "horses.h" #include <bits/stdc++.h> #define ff first #define ss second using namespace std; const int MAXN = (int) 5e5 + 5; const int mod = (int) 1e9+7; typedef long long ll; typedef pair<ll, ll> pll; ll x[MAXN], y[MAXN], pre[MAXN], n; set<pll> st; ll bp(ll a, ll b){ ll res = 1; while(b){ if(b % 2) res = (res * a) % mod; a = (a * a) % mod; b = b / 2; } return res; } ll t[4*MAXN]; void build(int v, int l, int r){ if(l == r){ t[v] = y[l];} else{ int m = (l + r) / 2; build(2*v, l, m); build(2*v + 1, m + 1, r); t[v] = max(t[2*v], t[2*v + 1]); } } void upd(int v, int tl, int tr, int pos){ if(tl == tr){ t[v] = y[tl]; }else{ int tm = (tl + tr) / 2; if(pos <= tm) upd(2*v, tl, tm, pos); else upd(2*v + 1, tm + 1, tr, pos); t[v] = max(t[2*v], t[2*v + 1]); } } ll que(int v, int tl , int tr, int l, int r){ if(l > r) return 0; else if(tl == l && tr == r) return t[v]; else{ int tm = (tl + tr) / 2; return max(que(2*v, tl, tm, l, min(tm, r)), que(2*v + 1, tm + 1, tr, max(tm + 1, l), r)); } } ll ft[MAXN]; void updi(int v, int val){ for(; v < MAXN; v += (v&-v)){ ft[v] = (ft[v] * val) % mod; } } ll get(int v){ ll res = 1; for(; v; v -= (v&-v)){ res = (res * ft[v]) % mod; } return res; } ll gt(){ ll top = 1; ll mx = 0; auto u = st.end(); do{ u--; top *= (*u).ss; } while(u != st.begin() && top < mod); top = 1; auto v = u; //cerr<<(*u).ff<<" "<<(*u).ss.ff<<endl; for(; u != st.end(); u++){ if(u != v) top *= (*u).ss; int l = (*u).ff; int r = (next(u) == st.end() ? n : (*next(u)).ff - 1); mx = max(mx, top*que(1, 0, n, l, r)); //cerr<<l<<" "<<r<<" "<<mx<<endl; } mx %= mod; return get((*v).ff) * mx % mod; } int init(int N, int X[], int Y[]) { n = N; for(int i = 0; i <= n; i++) ft[i] = 1; for(int i = 1; i <= n; i++){ x[i] = X[i - 1]; y[i] = Y[i - 1]; if(x[i] == 1){ if(!st.empty() && (*st.rbegin()).ss == 1){ }else{ st.insert({i, x[i]}); } }else{ st.insert({i, x[i]}); } updi(i, x[i]); } for(int i = 1; i <= n; i++){ pre[i] = pre[i - 1] * x[i] % mod; } build(1, 0, n); return gt(); } int updateX(int pos, int val) { pos++; updi(pos, bp(x[pos], mod - 2)*val % mod); if(x[pos] == val){ }else if(x[pos] == 1){ x[pos] = val; auto u = prev(st.upper_bound({pos, mod})); int l = (*u).ff; int r; if(next(u) == st.end()){ r = n; }else{ r = (*next(u)).ff - 1; } st.erase(u); if(l != pos) st.insert({l, 1}); if(r != pos) st.insert(make_pair(pos + 1, 1)); st.insert({pos, val}); }else{ if(val == 1){ auto u = st.lower_bound({pos, x[pos]}); st.erase(u); x[pos] = val; auto v = st.insert({pos, 1}).ff; if(v != st.end()){ u = v; u++; if((*u).ss == 1){ st.erase(u); } } if(v != st.begin()){ u = v; u--; if((*u).ss == 1){ st.erase(v); } } }else{ auto u = st.lower_bound({pos, x[pos]}); st.erase(u); x[pos] = val; st.insert({pos, x[pos]}); } } return gt(); } int updateY(int pos, int val) { pos++; y[pos] = val; upd(1, 0, n, pos); return gt(); }

Compilation message (stderr)

horses.cpp: In function 'll gt()':
horses.cpp:3:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    3 | #define ff first
      |            ^
horses.cpp:89:16: note: in expansion of macro 'ff'
   89 |   int l = (*u).ff;
      |                ^~
horses.cpp:90:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |   int r = (next(u) == st.end() ? n : (*next(u)).ff - 1);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:90:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:91:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |   mx = max(mx, top*que(1, 0, n, l, r));
      |                              ^
horses.cpp:3:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    3 | #define ff first
      |            ^
horses.cpp:95:18: note: in expansion of macro 'ff'
   95 |  return get((*v).ff) * mx % mod;
      |                  ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:114:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   updi(i, x[i]);
      |           ~~~^
horses.cpp:121:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  121 |  build(1, 0, n);
      |              ^
horses.cpp:122:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |  return gt();
      |         ~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:129:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  129 |  updi(pos, bp(x[pos], mod - 2)*val % mod);
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:3:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    3 | #define ff first
      |            ^
horses.cpp:136:16: note: in expansion of macro 'ff'
  136 |   int l = (*u).ff;
      |                ^~
horses.cpp:139:8: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |    r = n;
      |        ^
horses.cpp:141:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |    r = (*next(u)).ff - 1;
      |        ~~~~~~~~~~~~~~^~~
horses.cpp:176:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  176 |  return gt();
      |         ~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:182:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  182 |  upd(1, 0, n, pos);
      |            ^
horses.cpp:183:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  183 |  return gt();
      |         ~~^~
#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...