Submission #790912

#TimeUsernameProblemLanguageResultExecution timeMemory
790912KhizriHorses (IOI15_horses)C++17
17 / 100
1034 ms52872 KiB
#include "horses.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) const int mxn=5e5+5; ll n,idx[mxn],arr[mxn],tree2[mxn*4]; ll tree[4*mxn]; set<int>st; void build(int node,int l,int r){ if(l==r){ tree[node]=idx[l]; return; } int m=(l+r)/2; build(2*node,l,m); build(2*node+1,m+1,r); tree[node]=(tree[2*node]*tree[2*node+1])%MOD; } void build2(int node,int l,int r){ if(l==r){ tree2[node]=arr[l]; return; } int m=(l+r)/2; build2(2*node,l,m); build2(2*node+1,m+1,r); tree2[node]=max(tree2[2*node],tree2[2*node+1]); } void update(int node,int l,int r,int pos,int val){ if(l>pos||r<pos) return; if(l==r){ tree[node]=val; return; } int m=(l+r)/2; update(2*node,l,m,pos,val); update(2*node+1,m+1,r,pos,val); tree[node]=(tree[2*node]*tree[2*node+1])%MOD; } void update2(int node,int l,int r,int pos,int val){ if(l>pos||r<pos) return; if(l==r){ tree2[node]=val; return; } int m=(l+r)/2; update2(2*node,l,m,pos,val); update2(2*node+1,m+1,r,pos,val); tree2[node]=max(tree2[2*node],tree2[2*node+1]); } ll query(int node,int l,int r,int ql,int qr){ if(l>qr||r<ql) return 1; if(ql<=l&&r<=qr) return tree[node]; int m=(l+r)/2; return (query(2*node,l,m,ql,qr)*query(2*node+1,m+1,r,ql,qr))%MOD; } int query2(int node,int l,int r,int ql,int qr){ if(l>qr||r<ql) return 0; if(ql<=l&&r<=qr) return tree2[node]; int m=(l+r)/2; return max(query2(2*node,l,m,ql,qr),query2(2*node+1,m+1,r,ql,qr)); } int init(int N, int X[], int Y[]) { n=N; for(int i=0;i<n;i++){ arr[i+1]=Y[i]; idx[i+1]=X[i]; if(idx[i+1]>1){ st.insert(i+1); } } build(1,1,n); build2(1,1,n); int k=min(32,(int)st.size()); auto it=--st.end(); int res=query2(1,1,n,1,n); for(int x=1;x<=n;x++){ //int x=*it; ll ans=(query(1,1,n,1,x)*arr[x]); res=max(res,(int)ans); } return res%MOD; } int updateX(int pos, int val) { pos++; if(idx[pos]>1){ st.erase(pos); } idx[pos]=val; if(idx[pos]>1){ st.insert(pos); } update(1,1,n,pos,val); int k=min(33,(int)st.size()); auto it=--st.end(); int res=query2(1,1,n,1,n); while(k--){ int x=*it; ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD; res=max(res,(int)ans); it--; } return res; } int updateY(int pos, int val) { pos++; arr[pos]=val; update2(1,1,n,pos,val); int k=min(33,(int)st.size()); auto it=--st.end(); int res=query2(1,1,n,1,n); while(k--){ int x=*it; ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD; res=max(res,(int)ans); it--; } return res; }

Compilation message (stderr)

horses.cpp: In function 'int query2(int, int, int, int, int)':
horses.cpp:69:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   69 |     if(ql<=l&&r<=qr) return tree2[node];
      |                             ~~~~~~~~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |  build(1,1,n);
      |            ^
horses.cpp:83:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  build2(1,1,n);
      |             ^
horses.cpp:86:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  int res=query2(1,1,n,1,n);
      |                     ^
horses.cpp:86:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  int res=query2(1,1,n,1,n);
      |                         ^
horses.cpp:89:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |         ll ans=(query(1,1,n,1,x)*arr[x]);
      |                           ^
horses.cpp:84:6: warning: unused variable 'k' [-Wunused-variable]
   84 |  int k=min(32,(int)st.size());
      |      ^
horses.cpp:85:7: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   85 |  auto it=--st.end();
      |       ^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:104:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |  update(1,1,n,pos,val);
      |             ^
horses.cpp:107:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |  int res=query2(1,1,n,1,n);
      |                     ^
horses.cpp:107:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |  int res=query2(1,1,n,1,n);
      |                         ^
horses.cpp:110:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |         ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD;
      |                           ^
horses.cpp:110:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |         ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD;
      |                                             ^
horses.cpp:110:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |         ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD;
      |                                                 ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:120:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  update2(1,1,n,pos,val);
      |              ^
horses.cpp:123:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  int res=query2(1,1,n,1,n);
      |                     ^
horses.cpp:123:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |  int res=query2(1,1,n,1,n);
      |                         ^
horses.cpp:126:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |         ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD;
      |                           ^
horses.cpp:126:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |         ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%MOD;
      |                                             ^
horses.cpp:126:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |         ll ans=(query(1,1,n,1,x)*query2(1,1,n,x,n))%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...