Submission #541987

#TimeUsernameProblemLanguageResultExecution timeMemory
541987adamjinweiHorses (IOI15_horses)C++14
100 / 100
449 ms50232 KiB
#include <bits/stdc++.h> #include "horses.h" #define inf 1000000007 #define mod 1000000007 #define lson (p<<1) #define rson (p<<1|1) #define lowbit(x) (x&(-x)) // #define int long long // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") using namespace std; template <typename T> void read(T &x){ x=0;char ch=getchar();int fh=1; while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();} while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); x*=fh; } template <typename T> void write(T x) { if (x<0) x=-x,putchar('-'); if (x>9) write(x/10); putchar(x%10+'0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n,m; int x[500005],y[500005]; long long bit[500005]; pair<double,int> mx[2000005]; double tag[2000005]; long long qpow(long long a,long long b) { long long res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void bitmodify(int x,long long y) { while(x<=n) { bit[x]*=y; bit[x]%=mod; x+=lowbit(x); } } long long bitquery(int x) { long long res=1; while(x) { res*=bit[x]; res%=mod; x-=lowbit(x); } return res; } void build(int p,int l,int r) { if(l==r) { mx[p]={0,l}; return; } int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); mx[p]=max(mx[lson],mx[rson]); } void pushdown(int p) { mx[lson].first+=tag[p],tag[lson]+=tag[p]; mx[rson].first+=tag[p],tag[rson]+=tag[p]; tag[p]=0; } void modify(int p,int l,int r,int x,int y,double k) { if(x<=l&&r<=y) { mx[p].first+=k,tag[p]+=k; return; } int mid=l+r>>1; pushdown(p); if(x<=mid) modify(lson,l,mid,x,y,k); if(mid+1<=y) modify(rson,mid+1,r,x,y,k); mx[p]=max(mx[lson],mx[rson]); } int init(int N,int X[],int Y[]) { n=N; for(int i=1;i<=n;++i) { x[i]=X[i-1];bit[i]=1; } for(int i=1;i<=n;++i) y[i]=Y[i-1]; build(1,1,n); for(int i=1;i<=n;++i) { bitmodify(i,x[i]); modify(1,1,n,i,n,log(x[i])/log(2)); modify(1,1,n,i,i,log(y[i])/log(2)); } return (bitquery(mx[1].second)*y[mx[1].second]%mod); } int updateX(int pos,int val) { ++pos; bitmodify(pos,qpow(x[pos],mod-2)); bitmodify(pos,val); modify(1,1,n,pos,n,-log(x[pos])/log(2)); modify(1,1,n,pos,n,log(val)/log(2)); x[pos]=val; return (bitquery(mx[1].second)*y[mx[1].second]%mod); } int updateY(int pos,int val) { ++pos; modify(1,1,n,pos,pos,-log(y[pos])/log(2)); modify(1,1,n,pos,pos,log(val)/log(2)); y[pos]=val; return (bitquery(mx[1].second)*y[mx[1].second]%mod); }

Compilation message (stderr)

horses.cpp: In function 'void bitmodify(int, long long int)':
horses.cpp:43:32: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   43 | void bitmodify(int x,long long y)
      |                      ~~~~~~~~~~^
horses.cpp:28:15: note: shadowed declaration is here
   28 | int x[500005],y[500005];
      |               ^
horses.cpp:43:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   43 | void bitmodify(int x,long long y)
      |                ~~~~^
horses.cpp:28:5: note: shadowed declaration is here
   28 | int x[500005],y[500005];
      |     ^
horses.cpp: In function 'long long int bitquery(int)':
horses.cpp:52:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   52 | long long bitquery(int x)
      |                    ~~~~^
horses.cpp:28:5: note: shadowed declaration is here
   28 | int x[500005],y[500005];
      |     ^
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=l+r>>1;
      |          ~^~
horses.cpp: In function 'void modify(int, int, int, int, int, double)':
horses.cpp:81:41: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   81 | void modify(int p,int l,int r,int x,int y,double k)
      |                                     ~~~~^
horses.cpp:28:15: note: shadowed declaration is here
   28 | int x[500005],y[500005];
      |               ^
horses.cpp:81:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   81 | void modify(int p,int l,int r,int x,int y,double k)
      |                               ~~~~^
horses.cpp:28:5: note: shadowed declaration is here
   28 | int x[500005],y[500005];
      |     ^
horses.cpp:88:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int mid=l+r>>1;
      |          ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:110:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |  return (bitquery(mx[1].second)*y[mx[1].second]%mod);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return (bitquery(mx[1].second)*y[mx[1].second]%mod);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |  return (bitquery(mx[1].second)*y[mx[1].second]%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...