제출 #669694

#제출 시각아이디문제언어결과실행 시간메모리
669694victor_gao말 (IOI15_horses)C++17
100 / 100
462 ms85824 KiB
#include "horses.h" #include <bits/stdc++.h> #define ll long long #define pii pair<ll,ll> #define x first #define y second #define MAXN 500015 #define mod 1000000007 using namespace std; int dx[MAXN],dy[MAXN],n; ll fast_pow(ll a,ll b){ ll ans=1; while (b){ if (b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } struct segtree{ ll pos[4*MAXN],val[4*MAXN],val_x[4*MAXN],fac[4*MAXN]; pii remain[4*MAXN]; ll get_val(ll a=1,ll b=1,ll c=1,ll d=1){ vector<ll>vt={a,b,c,d}; ll ans=1; for (ll i:vt){ ans=ans*i; if (ans>1e9) return 1e9+2; } return ans; } void pull(int i){ fac[i]=fac[2*i]*fac[2*i+1]%mod; if (get_val(remain[2*i].y,remain[2*i+1].x,val_x[2*i+1],val[2*i+1])>val[2*i]){ pos[i]=pos[2*i+1]; val[i]=val[2*i+1]; remain[i].y=remain[2*i+1].y; val_x[i]=val_x[2*i+1]; remain[i].x=get_val(remain[2*i].x,remain[2*i].y,val_x[2*i],remain[2*i+1].x); } else { pos[i]=pos[2*i]; val[i]=val[2*i]; remain[i].x=remain[2*i].x; val_x[i]=val_x[2*i]; remain[i].y=get_val(remain[2*i].y,remain[2*i+1].x,remain[2*i+1].y,val_x[2*i+1]); } } void build(int l,int r,int i){ if (l==r){ remain[i]={1,1}; pos[i]=l; val[i]=dy[l]; fac[i]=dx[l]; val_x[i]=dx[l]; return; } int mid=(l+r)>>1; build(l,mid,2*i); build(mid+1,r,2*i+1); pull(i); } void modify_Y(int l,int r,int i,int p,ll c){ if (l==r){ val[i]=val[i]*c%mod; return; } int mid=(l+r)>>1; if (p<=mid) modify_Y(l,mid,2*i,p,c); else modify_Y(mid+1,r,2*i+1,p,c); pull(i); } void modify_X(int l,int r,int i,int p,ll c){ if (l==r){ fac[i]=fac[i]*c%mod; val_x[i]=val_x[i]*c%mod; return; } int mid=(l+r)>>1; if (p<=mid) modify_X(l,mid,2*i,p,c); else modify_X(mid+1,r,2*i+1,p,c); pull(i); } ll query(int l,int r,int i,int ql,int qr){ if (ql<=l&&qr>=r) return fac[i]; int mid=(l+r)>>1; if (qr<=mid) return query(l,mid,2*i,ql,qr); else if (ql>mid) return query(mid+1,r,2*i+1,ql,qr); else return query(l,mid,2*i,ql,qr)*query(mid+1,r,2*i+1,ql,qr)%mod; } void debug(int l,int r,int i){ cout<<l<<" ~ "<<r<<" : "<<fac[i]<<" best "<<pos[i]<<","<<val[i]<<","<<val_x[i]<<" remain : "<<remain[i].x<<' '<<remain[i].y<<'\n'; if (l==r) return; int mid=(l+r)>>1; debug(l,mid,2*i); debug(mid+1,r,2*i+1); } }seg; int init(int N, int X[], int Y[]) { n=N; for (int i=1;i<=n;i++){ dx[i]=X[i-1]; dy[i]=Y[i-1]; } seg.build(1,n,1); ll best=seg.pos[1]; ll ans=seg.query(1,n,1,1,best)*dy[best]%mod; return ans; } int updateX(int pos, int val) { pos++; ll inv=fast_pow(dx[pos],mod-2); dx[pos]=val; seg.modify_X(1,n,1,pos,inv); seg.modify_X(1,n,1,pos,val); ll best=seg.pos[1]; ll ans=seg.query(1,n,1,1,best)*dy[best]%mod; //cout<<"modify_X "<<best<<" "<<ans<<'\n'; //seg.debug(1,n,1); return ans; } int updateY(int pos, int val) { pos++; ll inv=fast_pow(dy[pos],mod-2); dy[pos]=val; seg.modify_Y(1,n,1,pos,inv); seg.modify_Y(1,n,1,pos,val); ll best=seg.pos[1]; ll ans=seg.query(1,n,1,1,best)*dy[best]%mod; //cout<<"modify_Y "<<best<<" "<<ans<<'\n'; //seg.debug(1,n,1); return ans; }

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

horses.cpp: In member function 'long long int segtree::get_val(long long int, long long int, long long int, long long int)':
horses.cpp:29:8: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   29 |    if (ans>1e9) return 1e9+2;
      |        ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                           ^~~~
horses.cpp:99:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:109:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |  ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                           ^~~~
horses.cpp:112:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |  ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                           ^~~~
horses.cpp:125:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  125 |  return ans;
      |         ^~~
#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...