제출 #40275

#제출 시각아이디문제언어결과실행 시간메모리
40275szawinis말 (IOI15_horses)C++14
17 / 100
129 ms74680 KiB
#include "horses.h" #include <algorithm> #include <cmath> using namespace std; using ll = long long; const int N = 1 << 19, MOD = 1e9+7; ll modPow(ll b, ll e) { if(!e) return 1; if(e == 1) return b; return modPow(b*b % MOD, e >> 1) * modPow(b, e & 1) % MOD; } struct node { long double comp; ll val; bool lazy_needed; void merge(node rhs) { lazy_needed = true; comp += rhs.comp; val = (val * rhs.val) % MOD; } bool operator>(const node& rhs) const { if(comp > rhs.comp) return true; if(val > rhs.val) return true; return false; } } t[2*N], lz[2*N]; void build(int i, int l, int r) { if(l == r) return; int mid = l+r >> 1; build(i<<1, l, mid); build(i<<1|1, mid+1, r); if(t[i<<1] > t[i<<1|1]) t[i] = t[i<<1]; else t[i] = t[i<<1|1]; } void apply(int i) { t[i].merge(lz[i]); if(i < N) { lz[i<<1].merge(lz[i]); lz[i<<1|1].merge(lz[i]); } lz[i].lazy_needed = false; lz[i].comp = 0, lz[i].val = 1; } void update(int i, int l, int r, int tl, int tr, node v) { if(lz[i].lazy_needed) apply(i); if(l > tr || r < tl) return; if(l >= tl && r <= tr) { lz[i].merge(v); apply(i); return; } int mid = l+r >> 1; update(i<<1, l, mid, tl, tr, v); update(i<<1|1, mid+1, r, tl, tr, v); if(t[i<<1] > t[i<<1|1]) t[i] = t[i<<1]; else t[i] = t[i<<1|1]; } int n, x[N], y[N]; int init(int _n, int _x[], int _y[]) { n = _n; copy(_x, _x+n, x); copy(_y, _y+n, y); node curr = {0, 1, 0}; for(int i = 0; i < n; i++) { curr.merge((node) {(long double) log2(x[i]), x[i]}); t[N+i] = curr; t[N+i].merge((node) {(long double) log2(y[i]), y[i]}); } build(1, 0, N-1); return t[1].val; } int updateX(int pos, int val) { long double ncomp = (long double) log2(val) - log2(x[pos]); ll nval = 1ll * val * modPow(x[pos], MOD-2) % MOD; update(1, 0, N-1, pos, N-1, (node) {ncomp, nval}); return t[1].val; } int updateY(int pos, int val) { long double ncomp = (long double) log2(val) - log2(y[pos]); ll nval = 1ll * val * modPow(y[pos], MOD-2) % MOD; update(1, 0, N-1, pos, pos, (node) {ncomp, nval}); return t[1].val; }

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

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
horses.cpp: In function 'void update(int, int, int, int, int, node)':
horses.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:52: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
   curr.merge((node) {(long double) log2(x[i]), x[i]});
                                                    ^
horses.cpp:73:54: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
   t[N+i].merge((node) {(long double) log2(y[i]), y[i]});
                                                      ^
horses.cpp:76:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].val;
              ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:49: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
  update(1, 0, N-1, pos, N-1, (node) {ncomp, nval});
                                                 ^
horses.cpp:83:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].val;
              ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:49: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
  update(1, 0, N-1, pos, pos, (node) {ncomp, nval});
                                                 ^
horses.cpp:90:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].val;
              ^
#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...