제출 #309513

#제출 시각아이디문제언어결과실행 시간메모리
309513mihai145말 (IOI15_horses)C++14
17 / 100
566 ms40892 KiB
#include "horses.h" #include <set> #include <vector> #include <algorithm> const int YMAX = 1e9; const int MOD = 1e9 + 7; const int NMAX = 5e5; int n, x[NMAX + 2], y[NMAX + 2]; struct Aintx { int v[4 * NMAX]; void Build(int node, int st, int dr) { if(st == dr) { v[node] = x[st]; return ; } int mid = (st + dr) >> 1; Build(2 * node, st, mid); Build(2 * node + 1, mid + 1, dr); v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD; } void setx(int node, int st, int dr, int pos, int val) { if(st == dr) { v[node] = val; return; } int mid = (st + dr) >> 1; if(pos <= mid) setx(2 * node, st, mid, pos, val); else setx(2 * node + 1, mid + 1, dr, pos, val); v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD; } int queryx(int node, int st, int dr, int l, int r) { if(st > dr) return 0; if(l <= st && dr <= r) return v[node]; if(dr < l || st > r) return 1; int mid = (st + dr) >> 1; int ans1 = queryx(2 * node, st, mid, l, r); int ans2 = queryx(2 * node + 1, mid + 1, dr, l, r); return (1LL * ans1 * ans2) % MOD; } }; Aintx aintx; struct Ainty { int v[4 * NMAX]; void Build(int node, int st, int dr) { if(st == dr) { v[node] = y[st]; return ; } int mid = (st + dr) >> 1; Build(2 * node, st, mid); Build(2 * node + 1, mid + 1, dr); v[node] = std::max(v[2 * node], v[2 * node + 1]); } void sety(int node, int st, int dr, int pos, int val) { if(st == dr) { v[node] = val; return; } int mid = (st + dr) >> 1; if(pos <= mid) sety(2 * node, st, mid, pos, val); else sety(2 * node + 1, mid + 1, dr, pos, val); v[node] = std::max(v[2 * node], v[2 * node + 1]); } int queryy(int node, int st, int dr, int l, int r) { if(st > dr) return 0; if(l <= st && dr <= r) return v[node]; if(dr < l || st > r) return 0; int mid = (st + dr) >> 1; int ans1 = queryy(2 * node, st, mid, l, r); int ans2 = queryy(2 * node + 1, mid + 1, dr, l, r); return std::max(ans1, ans2); } }; Ainty ainty; std::set <int> s; int Query() { long long prod = 1LL; std::vector <int> pos; for(auto it : s) { pos.push_back(-it); prod *= x[-it]; if(prod >= YMAX) break; } int sz = (int)pos.size(); long long px = 1LL, mx = 0LL, py; for(int i = sz - 2; i >= 0; i--) { px *= x[pos[i]]; if(i) py = ainty.queryy(1, 0, n - 1, pos[i], pos[i - 1] - 1); else py = ainty.queryy(1, 0, n - 1, pos[i], n - 1); mx = std::max(mx, px * py); } if(pos.back() == -1) { py = ainty.queryy(1, 0, n - 1, 0, n - 1); return std::max(mx, py); } if(sz > 1) py = ainty.queryy(1, 0, n - 1, pos[sz - 1], pos[sz - 2] - 1); else py = ainty.queryy(1, 0, n - 1, pos[sz - 1], n - 1); return (1LL * std::max(mx, py) * aintx.queryx(1, 0, n - 1, 0, pos[sz - 1])) % MOD; } int init(int N, int X[], int Y[]) { n = N; for(int i = 0; i < n; i++) x[i] = X[i], y[i] = Y[i]; aintx.Build(1, 0, n - 1); ainty.Build(1, 0, n - 1); s.insert(1); for(int i = 0; i < n; i++) { if(x[i] > 1) { s.insert(-i); } } return Query(); } int updateX(int pos, int val) { if(x[pos] == val) return Query(); aintx.setx(1, 0, n - 1, pos, val); if(x[pos] > 1 && val == 1) s.erase(-pos); else if(x[pos] == 1 && val > 1) s.insert(-pos); x[pos] = val; return Query(); } int updateY(int pos, int val) { if(y[pos] == val) return Query(); ainty.sety(1, 0, n - 1, pos, val); y[pos] = val; return Query(); }

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In member function 'void Aintx::Build(int, int, int)':
horses.cpp:28:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   28 |             v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void Aintx::setx(int, int, int, int, int)':
horses.cpp:45:61: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |             v[node] = (1LL * v[2 * node] * v[2 * node + 1]) % MOD;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int Aintx::queryx(int, int, int, int, int)':
horses.cpp:63:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |             return (1LL * ans1 * ans2) % MOD;
      |                    ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int Query()':
horses.cpp:157:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  157 |             return std::max(mx, py);
      |                    ~~~~~~~~^~~~~~~~
horses.cpp:165:81: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  165 |     return (1LL * std::max(mx, py) * aintx.queryx(1, 0, n - 1, 0, pos[sz - 1])) % 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...