제출 #858144

#제출 시각아이디문제언어결과실행 시간메모리
858144Huseyn123말 (IOI15_horses)C++17
0 / 100
236 ms44628 KiB
#include <bits/stdc++.h> #include "horses.h" #define MAX 1000001 #define INF LLONG_MAX #define MOD 1000000007 #define mp make_pair #define mt make_tuple #define pb push_back #define ins insert #define ff first #define ss second #define gett(x,m) get<m>(x) #define all(a) a.begin(),a.end() #define lb(a,b) lower_bound(all(a),b) #define ub(a,b) upper_bound(all(a),b) #define sortv(a) sort(all(a)) #define sorta(a,sz) sort(a,a+sz) #define inputar(a,b){\ for(int i=0;i<b;i++){\ cin >> a[i];\ }\ } #define inputvec(a,b){\ for(int i=0;i<b;i++){\ ll num;\ cin >> num;\ a.pb(num);\ }\ } #define outputar(a,b){\ for(int i=0;i<b;i++){\ cout << a[i] << " ";\ }\ cout << "\n";\ } #define outputvec(a){\ for(auto x:a){\ cout << x << " ";\ }\ cout << "\n";\ } #define reset(a,n,v){\ for(int i=0;i<n;i++){\ a[i]=v;\ }\ } using namespace std; typedef long long ll; typedef unsigned long long ull; typedef tuple<ll,ll,ll> tll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; typedef double db; typedef long double ldb; int n; vector<ll> X1,Y1; struct segtree_mul{ int size; vector<ll> muls; void build(vector<ll> &a,int x,int lx,int rx){ if(rx-lx==1){ if(lx<(int)a.size()){ muls[x]=a[lx]; } return; } int m=(lx+rx)/2; build(a,2*x+1,lx,m); build(a,2*x+2,m,rx); muls[x]=muls[2*x+1]*muls[2*x+2]; muls[x]%=MOD; } void build(vector<ll> &a){ build(a,0,0,size); } void init(int n){ size=1; while(size<n){ size*=2; } muls.assign(2*size,1); } ll mul(int l,int r,int x,int lx,int rx){ if(lx>=r || rx<=l){ return 1; } if(lx>=l && rx<=r){ return muls[x]; } ll s1,s2; int m=(lx+rx)/2; s1=mul(l,r,2*x+1,lx,m); s2=mul(l,r,2*x+2,m,rx); return (s1*s2)%MOD; } ll mul(int l,int r){ return mul(l,r,0,0,size); } void set(int i,int v,int x,int lx,int rx){ if(rx-lx==1){ muls[x]=v; return; } int m=(lx+rx)/2; if(i<m){ set(i,v,2*x+1,lx,m); } else{ set(i,v,2*x+2,m,rx); } muls[x]=muls[2*x+1]*muls[2*x+2]; muls[x]%=MOD; } void set(int i,int v){ set(i,v,0,0,size); } }; segtree_mul st_mul; set<ll> b; int init(int N, int X[], int Y[]) { n=N; X1.resize(n); Y1.resize(n); b.ins(-1); for(int i=0;i<N;i++){ if(X[i]!=1){ b.ins(i); } X1[i]=X[i]; Y1[i]=Y[i]; } st_mul.init(n); st_mul.build(X1); ll h=n-1; ll cnt=0; vector<ll> a; while(h>=0){ if(X1[h]==1){ auto it=b.upper_bound(h); --it; h=*it; h++; } a.pb(h); h--; cnt++; if(cnt==60){ break; } } reverse(all(a)); ll sz=(ll)a.size(); ll h1=1; ll ind=0; for(int i=1;i<sz;i++){ if(h1>=MOD/X1[a[i]]){ h1=MOD; } else{ h1*=X1[a[i]]; } if(h1>=Y1[a[ind]]/Y1[a[i]]){ ind=i; h1=1; } } ll res1=st_mul.mul(0,ind+1)*Y1[a[ind]]; res1%=MOD; return res1; } int updateX(int pos, int val) { st_mul.set(pos,val); if(X1[pos]==1 && val!=1){ b.ins(pos); } else if(val==1){ b.erase(pos); } X1[pos]=val; ll h=n-1; ll cnt=0; vector<ll> a; while(h>=0){ if(X1[h]==1){ auto it=b.upper_bound(h); --it; h=*it; h++; } a.pb(h); h--; cnt++; if(cnt==60){ break; } } reverse(all(a)); ll sz=(ll)a.size(); ll h1=1; ll ind=0; for(int i=1;i<sz;i++){ if(h1>=MOD/X1[a[i]]){ h1=MOD; } else{ h1*=X1[a[i]]; } if(h1>=Y1[a[ind]]/Y1[a[i]]){ ind=i; h1=1; } } ll res1=st_mul.mul(0,ind+1)*Y1[a[ind]]; res1%=MOD; return res1; } int updateY(int pos, int val){ Y1[pos]=val; ll h=n-1; ll cnt=0; vector<ll> a; while(h>=0){ if(X1[h]==1){ auto it=b.upper_bound(h); --it; h=*it; h++; } a.pb(h); h--; cnt++; if(cnt==60){ break; } } reverse(all(a)); ll sz=(ll)a.size(); ll h1=1; ll ind=0; for(int i=1;i<sz;i++){ if(h1>=MOD/X1[a[i]]){ h1=MOD; } else{ h1*=X1[a[i]]; } if(h1>=Y1[a[ind]]/Y1[a[i]]){ ind=i; h1=1; } } ll res1=st_mul.mul(0,ind+1)*Y1[ind]; res1%=MOD; return res1; }

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

horses.cpp: In member function 'void segtree_mul::init(int)':
horses.cpp:76:19: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   76 |     void init(int n){
      |               ~~~~^
horses.cpp:55:5: note: shadowed declaration is here
   55 | int n;
      |     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:167:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  167 |  ll res1=st_mul.mul(0,ind+1)*Y1[a[ind]];
      |                       ~~~^~
horses.cpp:169:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  169 |  return res1;
      |         ^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:213:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  213 |  ll res1=st_mul.mul(0,ind+1)*Y1[a[ind]];
      |                       ~~~^~
horses.cpp:215:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  215 |  return res1;
      |         ^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:253:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  253 |  ll res1=st_mul.mul(0,ind+1)*Y1[ind];
      |                       ~~~^~
horses.cpp:255:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  255 |  return res1;
      |         ^~~~
#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...