Submission #396830

#TimeUsernameProblemLanguageResultExecution timeMemory
396830Kenzo_1114Horses (IOI15_horses)C++17
17 / 100
507 ms55364 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 500010; const long long int MOD = 1e9 + 7; int n; long long int x[MAXN], y[MAXN]; long long int seg[2][4 * MAXN]; set<int> s; void upd(bool f, int pos, int bg, int ed, int id, int val) { if(bg == ed){ seg[f][pos] = (!f) ? val : id; return; } int mid = (bg + ed) >> 1, l = 2 * pos, r = l + 1; if(id <= mid) upd(f, l, bg, mid, id, val); else upd(f, r, mid + 1, ed, id, val); if(!f) seg[f][pos] = (seg[f][l] * seg[f][r]) % MOD; else seg[f][pos] = (y[seg[f][l]] > y[seg[f][r]]) ? seg[f][l] : seg[f][r]; } int qry(bool f, int pos, int bg, int ed, int p, int q) { if(q < p || q < bg || ed < p) return (!f) ? 1 : 0; if(p <= bg && ed <= q) return seg[f][pos]; int mid = (bg + ed) >> 1, l = 2 * pos, r = l + 1; if(!f) return (qry(f, l, bg, mid, p, q) * qry(f, r, mid + 1, ed, p, q)) % MOD; l = qry(f, l, bg, mid, p, q); r = qry(f, r, mid + 1, ed, p, q); return (y[l] > y[r]) ? l : r; } int getAns() { set<int> :: iterator l, r; int k = 0; l = s.end(); while(k < 32 && l != s.begin()) k++, l--; r = l; r++; int i = 0; long long int prefX = 1; while(r != s.end()) { // printf("i = %d l = %d r = %d | ", i, *l, *r); int q = qry(1, 1, 1, n, *l + 1, *r - 1); if(prefX >= MOD || y[i] < prefX * y[q]) { prefX = 1; i = q; } prefX *= x[*r]; // printf("i = %d l = %d r = %d\n", i, *l, *r); if(prefX >= MOD || y[i] < prefX * y[*r]) { prefX = 1; i = *r; } l++, r++; } // printf("i = %d\n", i); return (qry(0, 1, 1, n, 1, i) * y[i]) % MOD; } int updateX(int id, int val) { id++; if(val > 1) s.insert(id); else s.erase(id); x[id] = val; upd(0, 1, 1, n, id, val); return getAns(); } int updateY(int id, int val) { id++; y[id] = val; upd(1, 1, 1, n, id, val); return getAns(); } int init(int N, int X[], int Y[]) { n = N; for(int i = n; i > 0; i--) x[i] = X[i - 1]; for(int i = n; i > 0; i--) y[i] = Y[i - 1]; for(int i = 1; i <= n; i++) { upd(0, 1, 1, n, i, x[i]); upd(1, 1, 1, n, i, y[i]); if(x[i] > 1) s.insert(i); } s.insert(0); s.insert(n + 1); return getAns(); }

Compilation message (stderr)

horses.cpp: In function 'int qry(bool, int, int, int, int, int)':
horses.cpp:27:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |  if(p <= bg && ed <= q)   return seg[f][pos];
      |                                  ~~~~~~~~~~^
horses.cpp:31:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   31 |  if(!f) return (qry(f, l, bg, mid, p, q) * qry(f, r, mid + 1, ed, p, q)) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getAns()':
horses.cpp:72:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |  return (qry(0, 1, 1, n, 1, i) * y[i]) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:103:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |   upd(0, 1, 1, n, i, x[i]);
      |                      ~~~^
horses.cpp:104:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |   upd(1, 1, 1, n, i, y[i]);
      |                      ~~~^
#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...