제출 #140496

#제출 시각아이디문제언어결과실행 시간메모리
140496SirCeness말 (IOI15_horses)C++14
17 / 100
1563 ms29352 KiB
#include "horses.h" #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define inside sl<=l&&r<=sr #define outside r<sl||sr<l #define orta ((l+r)>>1) #define INF 1000000009 #define mod 1000000007 #define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n"; #define bas(x) #x << ": " << x << " " #define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n"; #define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n"; #define orta ((l+r)>>1) using namespace std; typedef long long ll; double arr[500005]; ll arrmod[500005]; int st[4*500005]; double lazy[4*500005]; int n; int x[500005]; int y[500005]; ll us(ll a, ll b){ ll ans = 1; while (b){ if (b & 1){ ans *= a; ans %= mod; } a *= a; a %= mod; b >>= 1; } return ans; } ll inv(ll a){ return us(a, mod-2); } void push(int node){ lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; lazy[node] = 0; } int get(int node){ push(node); return st[node]; } double getval(int node, int l, int r, int ind){ if (l == r) return lazy[node] + arr[l]; else { if (ind <= orta){ return getval(node*2, l, orta, ind) + lazy[node]; } else return getval(node*2+1, orta+1, r, ind) + lazy[node]; } } void stc(int node, int l, int r){ if (l == r){ lazy[node] = 0; st[node] = l; } else { int m = orta; stc(node*2, l, m); stc(node*2+1, m+1, r); double val1 = getval(1, 0, n-1, st[node*2]); double val2 = getval(1, 0, n-1, st[node*2+1]); st[node] = (val1 > val2) ? st[node*2] : st[node*2+1]; lazy[node] = 0; } } int stq(int node, int l, int r, int sl, int sr){ if (inside) return get(node); else if (outside) return 0; else { push(node); int m = orta; int i1 = stq(node*2, l, m, sl, sr); int i2 = stq(node*2+1, m+1, r, sl, sr); return getval(1, 0, n-1, i1) > getval(1, 0, n-1, i2) ? i1 : i2; } } void stu(int node, int l, int r, int ind, double val){ if (l == r) arr[l] += val; else { push(node); int m = orta; if (ind <= m) stu(node*2, l, m, ind, val); else stu(node*2+1, m+1, r, ind, val); double val1 = getval(1, 0, n-1, st[node*2]); double val2 = getval(1, 0, n-1, st[node*2+1]); st[node] = (val1 > val2) ? st[node*2] : st[node*2+1]; } } void stul(int node, int l, int r, int sl, int sr, double val){ if (inside) lazy[node] += val; else if (outside) return; else { int m = orta; push(node); stul(node*2, l, m, sl, sr, val); stul(node*2+1, m+1, r, sl, sr, val); double val1 = getval(1, 0, n-1, st[node*2]); double val2 = getval(1, 0, n-1, st[node*2+1]); st[node] = (val1 > val2) ? st[node*2] : st[node*2+1]; } } int init(int N, int X[], int Y[]) { n = N; for (int i = 0; i < n; i++) x[i] = X[i]; for (int i = 0; i < n; i++) y[i] = Y[i]; double sum = 0; ll summod = 1; for (int i = 0; i < n; i++){ sum += log2(X[i]); arr[i] = sum + log2(Y[i]); summod *= X[i]; summod %= mod; arrmod[i] = (summod*Y[i])%mod; } //prarr(arr, n); stc(1, 0, n-1); //for (int i = 0; i < 3; i++) cout << getval(1, 0, n-1, i) << " "; cout << endl; return arrmod[stq(1, 0, n-1, 0, n-1)]; } int updateX(int pos, int val){ //stul(1, 0, n-1, 0, pos, log2(val)-log2(x[pos])); for (int i = 0; i < pos; i++){ arr[i] += log2(val)-log2(x[pos]); } for (int i = 0; i < pos; i++){ arrmod[i] *= inv(x[pos]); arrmod[i] %= mod; arrmod[i] *= (ll)val; arrmod[i] %= mod; } x[pos] = val; int maxi = 0; double maxx = 0; for (int i = 0; i < n; i++) { if (arr[i] > maxx) maxi = i, maxx = arr[i]; } return arrmod[maxi]; } int updateY(int pos, int val) { //cout << "update " << pos << " -> " << log2(val) - log2(y[pos]) << endl; stu(1, 0, n-1, pos, log2(val) - log2(y[pos])); //prarr(arr, 3); //for (int i = 0; i < 3; i++) cout << getval(1, 0, n-1, i) << " "; cout << endl; arrmod[pos] *= inv(y[pos]); arrmod[pos] %= mod; arrmod[pos] *= val; arrmod[pos] %= mod; y[pos] = val; return arrmod[stq(1, 0, n-1, 0, n-1)]; }

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:143:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[stq(1, 0, n-1, 0, n-1)];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:163:20: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[maxi];
         ~~~~~~~~~~~^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:176:38: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return arrmod[stq(1, 0, n-1, 0, n-1)];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
#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...