Submission #893713

#TimeUsernameProblemLanguageResultExecution timeMemory
893713yellowtoadHorses (IOI15_horses)C++17
17 / 100
1008 ms39524 KiB
#include "horses.h" #include <iostream> using namespace std; const long long mod = 1e9+7; long long n, a[500010], b[500010], node[2000010][3]; bool done; /* 0: x product 1: max x 2: max y */ void build(int id, int x, int y) { if (x == y) { node[id][0] = a[x]%mod; node[id][1] = a[x]; node[id][2] = b[x]; return; } int mid = (x+y)/2; build(id*2,x,mid); build(id*2+1,mid+1,y); node[id][0] = (node[id*2][0]*node[id*2+1][0])%mod; node[id][1] = max(node[id*2][1],node[id*2+1][1]); node[id][2] = max(node[id*2][2],node[id*2+1][2]); } void update(int id, int jd, int x, int y, int pos, int val) { if (x == y) { node[id][jd] = val; return; } int mid = (x+y)/2; if (pos <= mid) update(id*2,jd,x,mid,pos,val); else update(id*2+1,jd,mid+1,y,pos,val); if (jd == 0) node[id][0] = (node[id*2][0]*node[id*2+1][0])%mod; else if (jd == 1) node[id][1] = max(node[id*2][1],node[id*2+1][1]); else node[id][2] = max(node[id*2][2],node[id*2+1][2]); } int nxt(int id, int x, int y, int r) { if (x > r) return 0; if (node[id][1] == 1) return 0; if (x == y) { done = 1; return x; } int mid = (x+y)/2, tmp = nxt(id*2+1,mid+1,y,r); if (!done) return nxt(id*2,x,mid,r); else return tmp; } long long find_max(int id, int x, int y, int l, int r) { if ((l <= x) && (y <= r)) return node[id][2]; if ((y < l) || (r < x)) return 0; int mid = (x+y)/2; return max(find_max(id*2,x,mid,l,r),find_max(id*2+1,mid+1,y,l,r)); } long long find_pro(int id, int x, int y, int l, int r) { if ((l <= x) && (y <= r)) return node[id][0]; if ((y < l) || (r < x)) return 1; int mid = (x+y)/2; return (find_pro(id*2,x,mid,l,r)*find_pro(id*2+1,mid+1,y,l,r))%mod; } long long solve() { long long cur = nxt(1,1,n,n)-1, lst = n, maxx = 1; while (maxx <= 1e9+7) { maxx = max(maxx,find_max(1,1,n,cur+1,lst)); lst = cur+1; maxx *= find_pro(1,1,n,lst,lst); done = 0; if (cur == -1) break; cur = nxt(1,1,n,cur)-1; } return ((maxx%mod)*find_pro(1,1,n,1,cur))%mod; } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++) a[i+1] = X[i], b[i+1] = Y[i]; build(1,1,n); return solve(); } int updateX(int pos, int val) { pos++; update(1,0,1,n,pos,val%mod); update(1,1,1,n,pos,val); return solve(); } int updateY(int pos, int val) { pos++; update(1,2,1,n,pos,val); return solve(); }

Compilation message (stderr)

horses.cpp: In function 'long long int solve()':
horses.cpp:70:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  long long cur = nxt(1,1,n,n)-1, lst = n, maxx = 1;
      |                          ^
horses.cpp:70:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |  long long cur = nxt(1,1,n,n)-1, lst = n, maxx = 1;
      |                            ^
horses.cpp:71:9: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   71 |  while (maxx <= 1e9+7) {
      |         ^~~~
horses.cpp:72:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   maxx = max(maxx,find_max(1,1,n,cur+1,lst));
      |                                ^
horses.cpp:72:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   maxx = max(maxx,find_max(1,1,n,cur+1,lst));
      |                                  ~~~^~
horses.cpp:72:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   maxx = max(maxx,find_max(1,1,n,cur+1,lst));
      |                                        ^~~
horses.cpp:74:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |   maxx *= find_pro(1,1,n,lst,lst);
      |                        ^
horses.cpp:74:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |   maxx *= find_pro(1,1,n,lst,lst);
      |                          ^~~
horses.cpp:74:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |   maxx *= find_pro(1,1,n,lst,lst);
      |                              ^~~
horses.cpp:77:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |   cur = nxt(1,1,n,cur)-1;
      |                 ^
horses.cpp:77:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |   cur = nxt(1,1,n,cur)-1;
      |                   ^~~
horses.cpp:79:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return ((maxx%mod)*find_pro(1,1,n,1,cur))%mod;
      |                                  ^
horses.cpp:79:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return ((maxx%mod)*find_pro(1,1,n,1,cur))%mod;
      |                                      ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:85:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |  build(1,1,n);
      |            ^
horses.cpp:86:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:91:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  update(1,0,1,n,pos,val%mod);
      |               ^
horses.cpp:92:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |  update(1,1,1,n,pos,val);
      |               ^
horses.cpp:93:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  update(1,2,1,n,pos,val);
      |               ^
horses.cpp:99:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |  return solve();
      |         ~~~~~^~
#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...