Submission #1025174

#TimeUsernameProblemLanguageResultExecution timeMemory
1025174YassirSalamaHorses (IOI15_horses)C++17
17 / 100
1592 ms21544 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define all(v) v.begin(),v.end() #define ll __int128_t template<typename T> void dbg_out(const T& t){ cout<<t<<endl; } template<typename T,typename... Args> void dbg_out(const T& t,const Args&... args){ cout<<t<<" , "; dbg_out(args...); } #define dbg(...) cout<<"("<<#__VA_ARGS__<<"): ";dbg_out(__VA_ARGS__); const ll mod=1e9+7; const int maxn=2000; int n; vector<ll> x; vector<ll> y; ll binpow(int a,int b){ ll ans=1; while(b){ if(b&1) ans=(ans%mod*a%mod)%mod; b>>=1; a=(a%mod*a%mod)%mod; } return ans; } ll invmod(int a){ return binpow(a,mod-2); } __int128_t ymx=1e18; __int128_t pref=1; ll solve(){ __int128_t ans=0; __int128_t suff=1; for(int i=n-1;i>=0;i--){ suff=max(suff,1LL*y[i]); if(suff>=ymx){ return (pref%mod*suff%mod)%mod; } suff*=x[i]; pref=((pref%mod)*invmod(x[i])%mod)%mod; } return suff%mod; } int init(int N, int X[], int Y[]) { n=N; x.resize(n,0); y.resize(n,0); for(int i=0;i<n;i++){ pref*=x[i]; pref%=mod; x[i]=X[i]; } for(int i=0;i<n;i++){ y[i]=Y[i]; } return (int)((ll)solve()%mod); } int updateX(int pos, int val) { pref=(pref%mod*invmod(x[pos])%mod)%mod; x[pos]=val; x[pos]%=mod; pref=(pref%mod*x[pos]%mod)%mod; return solve()%mod; } int updateY(int pos, int val) { y[pos]=val; y[pos]%=mod; return solve()%mod; } #ifdef IOI static char _buffer[1024]; static int _currentChar = 0; static int _charsNumber = 0; static FILE *_inputFile, *_outputFile; static inline int _read() { if (_charsNumber < 0) { exit(1); } if (!_charsNumber || _currentChar == _charsNumber) { _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile); _currentChar = 0; } if (_charsNumber <= 0) { return -1; } return _buffer[_currentChar++]; } static inline int _readInt() { int c, x, s; c = _read(); while (c <= 32) c = _read(); x = 0; s = 1; if (c == '-') { s = -1; c = _read(); } while (c > 32) { x *= 10; x += c - '0'; c = _read(); } if (s < 0) x = -x; return x; } int main() { // _inputFile = fopen("horses.in", "rb"); // _outputFile = fopen("horses.out", "w"); int N; cin>>N; int *X = (int*)malloc(sizeof(int)*(unsigned int)N); int *Y = (int*)malloc(sizeof(int)*(unsigned int)N); for (int i = 0; i < N; i++) { cin>>X[i]; } for (int i = 0; i < N; i++) { cin>>Y[i]; } cout<<init(N,X,Y)<<endl; int M; // M = _readInt(); cin>>M; for (int i = 0; i < M; i++) { int type; int pos; int val; cin>>type>>pos>>val; if (type == 1) { cout<<updateX(pos,val)<<endl; // fprintf(_outputFile,"%d\n",updateX(pos,val)); } else if (type == 2) { cout<<updateY(pos,val)<<endl; // fprintf(_outputFile,"%d\n",updateY(pos,val)); } } return 0; } #endif

Compilation message (stderr)

horses.cpp: In function '__int128 binpow(int, int)':
horses.cpp:27:18: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
   27 |   a=(a%mod*a%mod)%mod;
      |     ~~~~~~~~~~~~~^~~~
horses.cpp: In function '__int128 solve()':
horses.cpp:45:34: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   45 |      pref=((pref%mod)*invmod(x[i])%mod)%mod;
      |                                  ^
horses.cpp:37:13: warning: unused variable 'ans' [-Wunused-variable]
   37 |  __int128_t ans=0;
      |             ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:65:30: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'} to 'int' may change value [-Wconversion]
   65 |  pref=(pref%mod*invmod(x[pos])%mod)%mod;
      |                              ^
horses.cpp:69:16: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
   69 |  return solve()%mod;
      |         ~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:75:16: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
   75 |  return solve()%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...