# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
343281 | fixikmila | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++14 | 124 ms | 16472 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
if(b==0)return 1;
if(b%2==0){
ll t=bin_pow(a,b/2);
return t*t%MOD;
}
else return a*bin_pow(a,b-1)%MOD;
}
struct cat{ll a,b;};
cat tree[20001];
ll a[1000000];
void build_tree(ll v,ll tl,ll tr){
if(tl==tr)tree[v].a=tl,tree[v].b=a[tl];
else{
ll tm=(tl+tr)/2;
build_tree(2*v,tl,tm),build_tree(2*v+1,tm+1,tr);
if(tree[2*v].b>tree[2*v+1].b)tree[v].a=tree[2*v].a,tree[v].b=tree[2*v].b;
else tree[v].a=tree[2*v+1].a,tree[v].b=tree[2*v+1].b;
}
}
cat get_max(ll l,ll r,ll v,ll tl,ll tr){
if(tl>=l&&tr<=r)return tree[v];
else if(tl>r||tr<r){
cat f;
f.b=LLONG_MIN;
return f;
}
ll tm=(tl+tr)/2;
cat f=get_max(l,r,2*v,tl,tm),f1=get_max(l,r,2*v+1,tm+1,tr),f2;
if(f.b>f1.b)f2.a=f.a,f2.b=f.b;
else f2.a=f1.a,f2.b=f1.b;
return f2;
}
int main()
{
//freopen("stones.in","r",stdin);
//freopen("stones.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
cin>>n>>m;
vector<vector<ll>>c(1000);
for(int i=0;i<n;i++)cin>>a[i],mx=max(mx,a[i]);
//c[a[i]].push_back(i);
build_tree(1,0,n-1);
for(int i=0;i<m;i++){
cin>>l>>r>>k;
l--,r--;
z=1;
if(max(n,m)<=5e3){
ll mx1=-1;
set<ll>s;
for(int j=l;j<=r;j++){
auto u=s.lower_bound(a[j]);
if(u!=s.end()){
x=*u;
mx1=max(mx1,x+a[j]);
}
s.insert(a[j]);
}
if(mx1<=k)z=1;
else z=0;
}
else if(mx<=1e3){
y=-1;
ll mx1=-1,v;
for(int j=1;j<=1000;j++){
if(c[j].size()==0)continue;
if(c[j][0]>r||c[j].back()<l)continue;
x=upper_bound(c[j].begin(),c[j].end(),r)-c[j].begin()-1;
t=c[j][x];
if(t<y){
mx1=max(mx1,j+v);
}
//cout<<t<<" "<<y<<endl;
y=t;
v=j;
}
if(mx1<=k)z=1;
else z=0;
}
else{
while(true){
if(r<l)break;
cat f=get_max(l,r,1,0,n-1);
if(f.a!=r){
z=0;
break;
}
r--;
}
}
cout<<z;
cout<<"\n";
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |