제출 #641876

#제출 시각아이디문제언어결과실행 시간메모리
641876QwertyPi말 (IOI15_horses)C++14
100 / 100
899 ms64368 KiB
#include "horses.h" #include <bits/stdc++.h> #define ll long long using namespace std; const ll MOD = 1e9 + 7; const ll MAXN = 5e5 + 11; ll x[MAXN], y[MAXN]; struct BIT{ ll bit[MAXN] = {0}, id; void init(ll id, ll (*f)(ll, ll)) { this->id = id; fill(bit, bit + MAXN, id); combine = f; } void add(ll pos, ll val){ pos++; for(ll i = pos; i < MAXN; i += i & -i){ bit[i] = combine(bit[i], val); } } ll qry(ll pos){ pos++; ll ret = id; for(ll i = pos; i; i -= i & -i){ ret = combine(ret, bit[i]); } return ret; } ll (*combine)(ll, ll); } bit_add, bit_mul; ll N; namespace RMQ{ ll t[MAXN * 4] = {0}; void upd(int pos, int val, int v = 0, int tl = 0, int tr = N - 1){ if(tl == tr){ t[v] = val; return; } int tm = (tl + tr) / 2; if(pos <= tm){ upd(pos, val, v * 2 + 1, tl, tm); }else{ upd(pos, val, v * 2 + 2, tm + 1, tr); } t[v] = std::max(t[v * 2 + 1], t[v * 2 + 2]); } ll max(int l, int r, int v = 0, int tl = 0, int tr = N - 1){ if(r < tl || tr < l) return 0; if(l <= tl && tr <= r) return t[v]; int tm = (tl + tr) / 2; return std::max(max(l, r, v * 2 + 1, tl, tm), max(l, r, v * 2 + 2, tm + 1, tr)); } }; set<ll> n1; ll add(ll x, ll y) { return x + y; } ll mul(ll x, ll y) { return x * y % MOD; } ll bp(ll a, ll b) { if(b == 0) return 1; return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD; } ll mi(ll a) { return bp(a, MOD - 2); } ll query() { ll ans = 0, rans = 1; ll c = 1; auto ptr = --n1.end(); while(ptr != n1.begin() && c <= MOD){ ptr--; c *= x[*ptr]; } c = 1; for(; ptr != --n1.end(); ptr++){ ll v = RMQ::max(*ptr, *next(ptr) - 1); if(c * v > ans){ ans = c * v; rans = bit_add.qry(*ptr) > 0 ? 0 : mul(bit_mul.qry(*ptr), v); } c *= x[*next(ptr)]; } return rans; } int init(int N, int X[], int Y[]) { ::N = N; bit_add.init(0, add); bit_mul.init(1, mul); for(int i = 0; i < N; i++) x[i] = X[i]; for(int i = 0; i < N; i++) y[i] = Y[i]; for(int i = 0; i < N; i++){ if(x[i] == MOD) bit_add.add(i, 1); else bit_mul.add(i, x[i]); } n1.insert(0); n1.insert(N); for(int i = 0; i < N; i++){ if(x[i] != 1) n1.insert(i); } for(int i = 0; i < N; i++){ RMQ::upd(i, y[i]); } return query(); } int updateX(int pos, int val) { if(x[pos] == MOD) bit_add.add(pos, -1); else bit_mul.add(pos, mi(x[pos])); if(x[pos] != 1 && pos != 0) n1.erase(pos); x[pos] = val; if(x[pos] == MOD) bit_add.add(pos, 1); else bit_mul.add(pos, x[pos]); if(x[pos] != 1) n1.insert(pos); return query(); } int updateY(int pos, int val) { y[pos] = val; RMQ::upd(pos, val); return query(); }

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

horses.cpp: In member function 'void BIT::init(long long int, long long int (*)(long long int, long long int))':
horses.cpp:16:15: warning: declaration of 'id' shadows a member of 'BIT' [-Wshadow]
   16 |  void init(ll id, ll (*f)(ll, ll)) {
      |               ^
horses.cpp:15:22: note: shadowed declaration is here
   15 |  ll bit[MAXN] = {0}, id;
      |                      ^~
horses.cpp: At global scope:
horses.cpp:42:63: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  void upd(int pos, int val, int v = 0, int tl = 0, int tr = N - 1){
      |                                                             ~~^~~
horses.cpp:55:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 |  ll max(int l, int r, int v = 0, int tl = 0, int tr = N - 1){
      |                                                       ~~^~~
horses.cpp: In function 'long long int add(long long int, long long int)':
horses.cpp:66:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   66 | ll add(ll x, ll y) { return x + y; }
      |                 ^
horses.cpp:12:13: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |             ^
horses.cpp:66:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   66 | ll add(ll x, ll y) { return x + y; }
      |           ^
horses.cpp:12:4: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |    ^
horses.cpp: In function 'long long int mul(long long int, long long int)':
horses.cpp:67:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   67 | ll mul(ll x, ll y) { return x * y % MOD; }
      |                 ^
horses.cpp:12:13: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |             ^
horses.cpp:67:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   67 | ll mul(ll x, ll y) { return x * y % MOD; }
      |           ^
horses.cpp:12:4: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |    ^
horses.cpp: In function 'long long int query()':
horses.cpp:80:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |   ll v = RMQ::max(*ptr, *next(ptr) - 1);
      |                   ^~~~
horses.cpp:80:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |   ll v = RMQ::max(*ptr, *next(ptr) - 1);
      |                         ~~~~~~~~~~~^~~
horses.cpp:80:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |   ll v = RMQ::max(*ptr, *next(ptr) - 1);
      |                                       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:90:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   90 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:38:4: note: shadowed declaration is here
   38 | ll N;
      |    ^
horses.cpp:109:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |   RMQ::upd(i, y[i]);
      |               ~~~^
horses.cpp:109:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |   RMQ::upd(i, y[i]);
      |                   ^
horses.cpp:111:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:122:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  RMQ::upd(pos, val);
      |                   ^
horses.cpp:128:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |  return query();
      |         ~~~~~^~
#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...