zhangshuo2008

9989

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 200010,M = 18;
int f[N][M];
int w[N];
int n,m;
void init()
{
for(int j=0;j<M;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
if(!j)f[i][j]=w[i];
else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
}
int query(int l,int r)
{
int len=r-l+1;
int k=log(len)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
init();
cin>>m;
while(m--)
{
int l,r;
cin>>l>>r;
cout<<query(l,r)<<endl;
}
}


#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+17;
struct node {
int l, r;
int ql, qr;
int sum;
}tr[N * 4];
int root[N],a[N],b[N];
int idx;
int n,q;
int build(int l, int r)
{
int u = ++idx, mid = l + r >> 1;
tr[u].ql = l, tr[u].qr = r;
if (l == r) return u;
tr[u].l = build(l, mid);
tr[u].r = build(mid + 1, r);
return u;
}
void pushup(int u)
{
tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;
}
int modify(int p, int x)
{
int u = ++idx;
tr[u].l = tr[p].l, tr[u].r = tr[p].r;
tr[u].ql = tr[p].ql, tr[u].qr = tr[p].qr;
tr[u].sum=tr[p].sum+1;
if (tr[u].ql == tr[u].qr)
{
return u;
}
int mid = tr[u].ql + tr[u].qr >> 1;
if (x <= mid)tr[u].l = modify(tr[p].l, x);
else tr[u].r = modify(tr[p].r, x);
return u;
}
int query(int u,int v, int k)
{
if(tr[u].ql>=tr[u].qr)return tr[u].ql;
int x=tr[tr[v].l].sum-tr[tr[u].l].sum;
int mid=tr[u].ql+tr[u].qr>>1;
if(x>=k) return query(tr[u].l,tr[v].l,k);
else return query(tr[u].r,tr[v].r,k-x);
}
void print(int u)
{
cout<<tr[u].ql<<" "<<tr[u].qr<<" "<<tr[u].sum<<endl;
if(tr[u].ql==tr[u].qr)return;
print(tr[u].l);
print(tr[u].r);
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int m=unique(b+1,b+1+n)-b-1;
root[0]=build(1,m);
for(int i=1;i<=n;i++)
{
int t=lower_bound(b+1,b+1+m,a[i])-b;
root[i]=modify(root[i-1],t);
}
while(q--)
{
int l,r,k;
cin>>l>>r>>k;
int t=query(root[l-1],root[r],k);
cout<<b[t]<<endl;
}
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 101011;
double s[N];
double a[N];
int n,F;
bool check(double avg)
{
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]-avg;
double mins=0;
for(int k=F;k<=n;k++)
{
mins=min(mins,s[k-F]);
if(s[k]-mins>=0)return true;
}
return false;
}

int main()
{
double l=0,r=0;
cin>>n>>F;
for(int i=1;i<=n;i++)
{
cin>>a[i];
r=max(r,a[i]);
}
while(r-l>1e-5)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%d",(int)(r*1000));
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
int s[N][N];
int main()
{
int n,r;
cin>>n>>r;
r=min(r,5002);
for(int i=1;i<=n;i++)
{
int x,y,w;
cin>>x>>y>>w;
x++,y++;
s[x][y]+=w;
}
for(int i=1;i<=5001;i++)
{
for(int j=1;j<=5001;j++)
{
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
int res=0;
for(int i=r;i<=5001;i++)
{
for(int j=r;j<=5001;j++)
{
res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
}
}
cout<<res<<endl;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int mod = 9901;
int qmi(int a,int k)
{
int res=1;
a%=mod;
while(k)
{
if(k&1)res=res*a%mod;
k>>=1;
a=a*a%mod;
}
return res;
}
int sum(int p,int k)
{
if(k==1)return 1;
if(k%2==0)return (1+qmi(p,k/2))*sum(p,k/2)%mod;
if(k%2==1)return (sum(p,k-1)+qmi(p,k-1))%mod;
}

int main()
{
int a,b;
cin>>a>>b;
int res=1;
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
{
int s=0;
while(a%i==0)
{
a/=i;
s++;
}
res=res*sum(i,b*s+1)%mod;
}
}
if(a>1)
{
res=res*sum(a,b+1)%mod;
}
if(a==0)cout<<0<<endl;
else cout<<res%mod;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
signed main()
{
int a,b,p,res=0;
cin>>a>>b>>p;
while(b)
{
if(b&1)res=(res+a)%p;
b>>=1;
a=2*a%p;
}
cout<<res<<endl;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int exgcd(int a, int b, int &x, int &y)  // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}

int main()
{
int T;
cin>>T;
while(T--)
{
int a,b,m,x,y;
cin>>a>>b>>m;
int d=exgcd(a,m,x,y);
if(b%d)puts("impossible");
else cout<<(long long)x*(b/d)%m<<endl;
}
}


#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int t=exgcd(b,a%b,y,x);
y=y-(a/b)*x;
return t;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int p=19260817;
char s1[10051], s2[10051];
int a,b;
int qmi(int a, int k, int p)
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (long long)res * a % p;
a = (long long)a * a % p;
k >>= 1;
}
return res;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
if(n%m==0)
{
puts("impossible");
continue;
}
else cout<<qmi(n,m-2,m)<<endl;
}
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>A;
vector<int>B;
string a,b;
// vector<int> add(vector<int> &A, vector<int> &B)  // C = A + B, A >= 0, B >= 0
// {
//     if (A.size() < B.size()) return add(B, A);

//     vector<int> C;
//     int t = 0;
//     for (int i = 0; i < A.size(); i ++ )
//     {
//         t += A[i];
//         if (i < B.size()) t += B[i];
//         C.push_back(t % 10);
//         t /= 10;
//     }

//     if (t) C.push_back(t);
//     return C;
// }

{
vector<int>c;
int t=0;
for(int i=0;i<A.size();i++)
{
t+=A[i];
if(i<B.size())t+=B[i];
c.push_back(t%10);
t/=10;
}
if(t)c.push_back(1);
return c;
}
int main()
{
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');