제출 #438512

#제출 시각아이디문제언어결과실행 시간메모리
438512adamjinwei말 (IOI15_horses)C++14
34 / 100
454 ms56152 KiB
#include <bits/stdc++.h> #include "horses.h" #define lowbit(x) (x&(-x)) #define lson (p<<1) #define rson (p<<1|1) #define inf 1000000007 #define mod 1000000007 #define rnd() rand_num() #define bigrnd() dis(rand_num) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #define int long long using namespace std; unsigned sed=std::chrono::system_clock::now().time_since_epoch().count(); mt19937 rand_num(sed); uniform_int_distribution<long long> dis(0,inf); 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; long long x[500005],y[500005]; long long bit[500005]; double mx[500005],tag[500005]; int mxid[500005]; 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 pushup(int p) { if(mx[lson]>mx[rson]) { mx[p]=mx[lson]; mxid[p]=mxid[lson]; } else { mx[p]=mx[rson]; mxid[p]=mxid[rson]; } } void build(int p,int l,int r) { if(l==r) { mx[p]=0; mxid[p]=l; return; } int mid=l+r>>1; build(lson,l,mid); build(rson,mid+1,r); pushup(p); } void pushdown(int p) { mx[lson]+=tag[p]; tag[lson]+=tag[p]; mx[rson]+=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]+=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); pushup(p); } signed init(signed N,signed X[],signed Y[]) { n=N; for(int i=1;i<=n;++i) { x[i]=X[i-1]; y[i]=Y[i-1]; bit[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(mxid[1])*y[mxid[1]]%mod; } signed updateX(signed pos,signed val) { pos++; modify(1,1,n,pos,n,-log(x[pos])/log(2)); modify(1,1,n,pos,n,log(val)/log(2)); bitmodify(pos,qpow(x[pos],mod-2)); bitmodify(pos,val); x[pos]=val; return bitquery(mxid[1])*y[mxid[1]]%mod; } signed updateY(signed pos,signed 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(mxid[1])*y[mxid[1]]%mod; }

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

horses.cpp:14:71: warning: conversion from 'std::chrono::duration<long int, std::ratio<1, 1000000000> >::rep' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
   14 | unsigned sed=std::chrono::system_clock::now().time_since_epoch().count();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
horses.cpp: In function 'void bitmodify(long long int, long long int)':
horses.cpp:48:32: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   48 | void bitmodify(int x,long long y)
      |                      ~~~~~~~~~~^
horses.cpp:33:21: note: shadowed declaration is here
   33 | long long x[500005],y[500005];
      |                     ^
horses.cpp:48:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   48 | void bitmodify(int x,long long y)
      |                    ^
horses.cpp:33:11: note: shadowed declaration is here
   33 | long long x[500005],y[500005];
      |           ^
horses.cpp: In function 'long long int bitquery(long long int)':
horses.cpp:57:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   57 | long long bitquery(int x)
      |                        ^
horses.cpp:33:11: note: shadowed declaration is here
   33 | long long x[500005],y[500005];
      |           ^
horses.cpp: In function 'void build(long long int, long long int, long long int)':
horses.cpp:89:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  int mid=l+r>>1;
      |          ~^~
horses.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, double)':
horses.cpp:102:41: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  102 | void modify(int p,int l,int r,int x,int y,double k)
      |                                         ^
horses.cpp:33:21: note: shadowed declaration is here
   33 | long long x[500005],y[500005];
      |                     ^
horses.cpp:102:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  102 | void modify(int p,int l,int r,int x,int y,double k)
      |                                   ^
horses.cpp:33:11: note: shadowed declaration is here
   33 | long long x[500005],y[500005];
      |           ^
horses.cpp:110:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |  int mid=l+r>>1;
      |          ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:132:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  return bitquery(mxid[1])*y[mxid[1]]%mod;
      |                                     ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:142:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  142 |  return bitquery(mxid[1])*y[mxid[1]]%mod;
      |                                     ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  150 |  return bitquery(mxid[1])*y[mxid[1]]%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...