제출 #485025

#제출 시각아이디문제언어결과실행 시간메모리
485025jeroenodb말 (IOI15_horses)C++14
17 / 100
88 ms32876 KiB
#include "horses.h" #include "bits/stdc++.h" #ifdef LOCAL #include "grader.cpp" #endif using namespace std; #define all(x) begin(x),end(x) typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1; const ll oo = 1e18; const long long MD = 1e9+7; template<long long MOD=MD> struct mdint { int d=0; mdint () {d=0;} mdint (long long _d) : d(_d%MOD){}; friend mdint& operator+=(mdint& a, const mdint& o) { a.d+=o.d; if(a.d>=MOD) a.d-=MOD; return a; } friend mdint& operator-=(mdint& a, const mdint& o) { a.d-=o.d; if(a.d<0) a.d+=MOD; return a; } friend mdint& operator*=(mdint& a, const mdint& o) { return a = mdint((ll)a.d*o.d); } mdint operator*(const mdint& o) const { mdint res = *this; res*=o; return res; } mdint operator+(const mdint& o) const { mdint res = *this; res+=o; return res; } mdint operator-(const mdint& o) const { mdint res = *this; res-=o; return res; } mdint operator^(long long b) const { mdint tmp = 1; mdint power = *this; while(b) { if(b&1) { tmp = tmp*power; } power = power*power; b/=2; } return tmp; } friend mdint operator/=(mdint& a, const mdint& o) { a *= (o^(MOD-2)); return a; } mdint operator/(const mdint& o) { mdint res = *this; res/=o; return res; } bool operator==(const mdint& o) { return d==o.d;} bool operator!=(const mdint& o) { return d!=o.d;} friend istream& operator>>(istream& c, mdint& a) {return c >> a.d;} friend ostream& operator<<(ostream& c, const mdint& a) {return c << a.d;} }; using mint = mdint<MD>; struct node { mint prod=1; ll mx=1, prodl=1; node() { } node(int x, int y) { mx = (ll)x*y; prod=x; prodl=x; } void merge(const node& o) { prod*=o.prod; if(o.mx and oo/o.mx < prodl) mx=oo; else mx = max(mx,o.mx*prodl); if(o.prodl and oo/o.prodl<prodl) prodl=oo; else prodl*=o.prodl; } friend node merge(node a, const node& b) { a.merge(b); return a; } }; struct segtree { int ptwo,n; vector<node> seg; segtree(){} node& operator[](int i) { return seg[i+ptwo]; } segtree(int nn) { ptwo=1<<__lg(2*nn-1); n=nn; seg.assign(ptwo*2,node(1,0)); } auto cutoff() { const int Cut = 1e9+1; if(seg[1].prodl>=Cut) return 0; int i=1; while(i<ptwo) { if(seg[i*2+1].prodl>=Cut) { i=i*2+1; } else i=i*2; } return i-ptwo; } auto query(int l, int r) { assert(l>=0 and l<ptwo and r >=0 and r<ptwo); l+=ptwo; r+=ptwo; node resl, resr; while(l and l<=r) { if(l%2==1) resl = merge(resl,seg[l++]); if(r%2==0) resr = merge(seg[r--],resr); l/=2; r/=2; } return merge(resl,resr); } void update(int i, int x, int y) { assert(i>=0 and i<ptwo); i+=ptwo; seg[i] = node(x,y); for(i/=2;i>=1;i/=2) { seg[i] = merge(seg[2*i],seg[2*i+1]); } } mint best() { auto i = cutoff(); if(i==0) { return query(0,n-1).mx; } return query(0,i-1).prod * query(i,n-1).mx; } void build() { for(int i=ptwo-1;i>=1;--i) { seg[i] = merge(seg[2*i],seg[2*i+1]); } } }; segtree seg; int *x, *y; int init(int N, int X[], int Y[]) { x=X,y=Y; seg = segtree(N); for(auto i=0;i<N;++i) { seg[i] = node(X[i],Y[i]); } seg.build(); return seg.best().d; } int updateX(int pos, int val) { x[pos]=val; seg.update(pos,x[pos],y[pos]); return seg.best().d; } int updateY(int pos, int val) { y[pos] = val; seg.update(pos,x[pos],y[pos]); return seg.best().d; }

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

horses.cpp: In instantiation of 'mdint<MOD>::mdint(long long int) [with long long int MOD = 1000000007]':
horses.cpp:73:15:   required from here
horses.cpp:18:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |     mdint (long long _d) : d(_d%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...