Submission #559495

#TimeUsernameProblemLanguageResultExecution timeMemory
559495joshjmsHorses (IOI15_horses)C++14
100 / 100
836 ms65544 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pb push_back #define fi first #define se second #define debug(x) cout << #x << " => " << x << "\n"; const long long mod = 1e9 + 7; ll n, x[500005], y[500005]; struct node { ll idx, val, nxt, prv; } arr[500005]; set <ll> st; ll tree[2000005]; void upd(ll idx, ll l, ll r, ll x, ll v) { if(l == r) { tree[idx] = v; return; } ll mid = (l + r) / 2; if(x <= mid) upd(idx * 2, l, mid, x, v); else upd(idx * 2 + 1, mid + 1, r, x, v); tree[idx] = (tree[idx * 2] * tree[idx * 2 + 1]) % mod; } ll query(ll idx, ll l, ll r, ll x, ll y) { if(l > r || l > y || r < x) return 1; if(l >= x && r <= y) return tree[idx]; ll mid = (l + r) / 2; return (query(idx * 2, l, mid, x, y) * query(idx * 2 + 1, mid + 1, r, x, y)) % mod; } ll maxy[2000005]; void updy(ll idx, ll l, ll r, ll x, ll v) { if(l == r) { maxy[idx] = v; return; } ll mid = (l + r) / 2; if(x <= mid) updy(idx * 2, l, mid, x, v); else updy(idx * 2 + 1, mid + 1, r, x, v); maxy[idx] = max(maxy[idx * 2], maxy[idx * 2 + 1]); } ll queryy(ll idx, ll l, ll r, ll x, ll y) { if(l > r || l > y || r < x) return 0; if(l >= x && r <= y) return maxy[idx]; ll mid = (l + r) / 2; return max(queryy(idx * 2, l, mid, x, y), queryy(idx * 2 + 1, mid + 1, r, x, y)); } int init(int N, int X[], int Y[]) { n = N; for(ll i = 1; i <= n; i++) { x[i] = X[i - 1]; y[i] = Y[i - 1]; upd(1, 1, n, i, x[i]); updy(1, 1, n, i, y[i]); } for(ll i = 1; i <= n; i++) { if(x[i] > 1) { st.insert(i); } } x[n + 1] = 1; st.insert(n + 1); x[0] = 1; st.insert(0); auto it = st.end(); pair <ll,ll> maxi = {0, 0}; vector <ll> tmp; for(ll mul = 1; it != st.begin();) { it--; mul *= x[*it]; tmp.pb(*it); if(mul > 1e9) break; } reverse(tmp.begin(), tmp.end()); for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) { ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1); maxi = max(maxi, {mul * max_y, tmp[i]}); mul *= x[tmp[i + 1]]; } auto nuit = st.upper_bound(maxi.se); return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod; } int updateX(int pos, int val) { pos++; x[pos] = val; if(x[pos] == 1) st.erase(pos); else st.insert(pos); upd(1, 1, n, pos, val); auto it = st.end(); pair <ll,ll> maxi = {0, 0}; vector <ll> tmp; for(ll mul = 1; it != st.begin();) { it--; mul *= x[*it]; tmp.pb(*it); if(mul > 1e9) break; } reverse(tmp.begin(), tmp.end()); for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) { ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1); maxi = max(maxi, {mul * max_y, tmp[i]}); mul *= x[tmp[i + 1]]; } auto nuit = st.upper_bound(maxi.se); return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod; } int updateY(int pos, int val) { pos++; y[pos] = val; updy(1, 1, n, pos, val); auto it = st.end(); pair <ll,ll> maxi = {0, 0}; vector <ll> tmp; for(ll mul = 1; it != st.begin();) { it--; mul *= x[*it]; tmp.pb(*it); if(mul > 1e9) break; } reverse(tmp.begin(), tmp.end()); for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) { ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1); maxi = max(maxi, {mul * max_y, tmp[i]}); mul *= x[tmp[i + 1]]; } auto nuit = st.upper_bound(maxi.se); return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod; } // static char _buffer[1024]; // static int _currentChar = 0; // static int _charsNumber = 0; // static FILE *_inputFile, *_outputFile; // static inline int _read() { // if (_charsNumber < 0) { // exit(1); // } // if (!_charsNumber || _currentChar == _charsNumber) { // _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile); // _currentChar = 0; // } // if (_charsNumber <= 0) { // return -1; // } // return _buffer[_currentChar++]; // } // static inline int _readInt() { // int c, x, s; // c = _read(); // while (c <= 32) c = _read(); // x = 0; // s = 1; // if (c == '-') { // s = -1; // c = _read(); // } // while (c > 32) { // x *= 10; // x += c - '0'; // c = _read(); // } // if (s < 0) x = -x; // return x; // } // int main() { // // _inputFile = fopen("horses.in", "rb"); // // _outputFile = fopen("horses.out", "w"); // int N; cin >> N; // int *X = (int*)malloc(sizeof(int)*(unsigned int)N); // int *Y = (int*)malloc(sizeof(int)*(unsigned int)N); // for (int i = 0; i < N; i++) { // cin >> X[i]; // } // for (int i = 0; i < N; i++) { // cin >> Y[i]; // } // // fprintf(_outputFile,"%d\n",init(N,X,Y)); // cout << init(N, X, Y) << "\n"; // int M; cin >> M; // for (int i = 0; i < M; i++) { // int type; cin >> type; // int pos; cin >> pos; // int val; cin >> val; // if (type == 1) { // cout << updateX(pos, val) << "\n"; // } else if (type == 2) { // cout << updateY(pos, val) << "\n"; // } // } // return 0; // } // int main() { // // _inputFile = fopen("horses.in", "rb"); // // _outputFile = fopen("horses.out", "w"); // int N; cin >> N; // int *X = (int*)malloc(sizeof(int)*(unsigned int)N); // int *Y = (int*)malloc(sizeof(int)*(unsigned int)N); // for (int i = 0; i < N; i++) { // cin >> X[i]; // } // for (int i = 0; i < N; i++) { // cin >> Y[i]; // } // // fprintf(_outputFile,"%d\n",init(N,X,Y)); // int M; cin >> M; // for (int i = 0; i < 7; i++) { // int type; cin >> type; // int pos; cin >> pos; // int val; cin >> val; // if (type == 1) { // X[pos] = val; // } else if (type == 2) { // Y[pos] = val; // } // } // cout << init(N, X, Y) << "\n"; // return 0; // }

Compilation message (stderr)

horses.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:25:33: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   25 | void upd(ll idx, ll l, ll r, ll x, ll v) {
      |                                 ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:36:39: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   36 | ll query(ll idx, ll l, ll r, ll x, ll y) {
      |                                       ^
horses.cpp:15:18: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |                  ^
horses.cpp:36:33: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   36 | ll query(ll idx, ll l, ll r, ll x, ll y) {
      |                                 ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'void updy(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:45:34: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   45 | void updy(ll idx, ll l, ll r, ll x, ll v) {
      |                                  ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'long long int queryy(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:56:40: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   56 | ll queryy(ll idx, ll l, ll r, ll x, ll y) {
      |                                        ^
horses.cpp:15:18: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |                  ^
horses.cpp:56:34: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   56 | ll queryy(ll idx, ll l, ll r, ll x, ll y) {
      |                                  ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:87:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   87 |         if(mul > 1e9) break;
      |            ^~~
horses.cpp:90:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
      |                            ~~^~~~~~~~~~~~~~~~
horses.cpp:96:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |     return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:112:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  112 |         if(mul > 1e9) break;
      |            ^~~
horses.cpp:115:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
      |                            ~~^~~~~~~~~~~~~~~~
horses.cpp:121:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |     return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:135:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  135 |         if(mul > 1e9) break;
      |            ^~~
horses.cpp:138:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
      |                            ~~^~~~~~~~~~~~~~~~
horses.cpp:144:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  144 |     return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 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...