제출 #40279

#제출 시각아이디문제언어결과실행 시간메모리
40279szawinis말 (IOI15_horses)C++14
17 / 100
127 ms58296 KiB
#include "horses.h" #include <algorithm> #include <cmath> using namespace std; using ll = long long; const int N = 1 << 19; const ll 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 { double comp; ll val; bool lazy_needed; void merge(node rhs) { lazy_needed = true; comp += rhs.comp; val = 1ll * val * rhs.val % MOD; } bool operator>(const node &rhs) const { if (comp > rhs.comp) return true; if (comp == rhs.comp && 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){(double)log2(x[i]), x[i]}); t[N + i] = curr; t[N + i].merge((node){(double)log2(y[i]), y[i]}); } build(1, 0, N - 1); return t[1].val; } int updateX(int pos, int val) { double ncomp = (double)log2(val) - (double)log2(x[pos]); ll nval = 1ll * val * modPow(x[pos], MOD - 2) % MOD; x[pos] = val; update(1, 0, N - 1, pos, N - 1, (node){ncomp, nval}); return t[1].val; } int updateY(int pos, int val) { double ncomp = (double)log2(val) - (double)log2(y[pos]); ll nval = 1ll * val * modPow(y[pos], MOD - 2) % MOD; y[pos] = val; 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:38:15: 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:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
               ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:83:47: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
     curr.merge((node){(double)log2(x[i]), x[i]});
                                               ^
horses.cpp:85:51: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
     t[N + i].merge((node){(double)log2(y[i]), y[i]});
                                                   ^
horses.cpp:88:15: 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:95:53: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
   update(1, 0, N - 1, pos, N - 1, (node){ncomp, nval});
                                                     ^
horses.cpp:96:15: 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:103:51: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
   update(1, 0, N - 1, pos, pos, (node){ncomp, nval});
                                                   ^
horses.cpp:104:15: 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...