이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define rep(i,n) for (int i = 1; i <= n; i++)
#define f first
#define s second
#define pb push_back
#define debug(x) cout<<#x<<" is "<<x<<endl;
const int N=100010;// log is ~17
int n,m,k,A,B,t[20][N][2],q;
struct node{
int s,e,m,v,lazy;
node *l, *r;
node(int S, int E){
s=S,e=E,m=(s+e)/2;
v=1e9;lazy=1e9;
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void prop(){
if(lazy==1e9)return;
v=min(lazy, v);
if(s!=e){
l->lazy= min(l->lazy, v);
r->lazy= min(r->lazy, v);
}
lazy=1e9;
}
void upd(int S, int E, int V){
if(s==S &&e==E) lazy= V;
else{
if(E<=m)l->upd(S,E,V);
else if(S>m) r->upd(S,E,V);
else{
l-> upd(S,m,V);
r->upd(m+1,E,V);
}
l-> prop();
r->prop();
v=min(l->v, r->v);
}
}
int rmin(int S, int E){
prop();
if(s==S&&e==E){
return v;
}
if(E<=m)return l->rmin(S,E);
if(S>m) return r->rmin(S,E);
return min(l-> rmin(S,m), r->rmin(m+1,E));
}
}*lroot[20];// stores minpos you can go from i using 1 train
struct nodee{
int s,e,m,v,lazy;
nodee *l, *r;
nodee(int S, int E){
s=S,e=E,m=(s+e)/2;
v=0;lazy=0;
if(s!=e){
l = new nodee(s,m);
r=new nodee(m+1,e);
}
}
void prop(){
if(lazy==0)return;
//debug (lazy) debug(v) debug(s) debug(e);
if(s!=e){
l->lazy= max(l->lazy, lazy);
r->lazy= max(r->lazy, lazy);
}
v=max(lazy, v);
lazy=0;
}
void upd(int S, int E, int V){
if(s==S &&e==E) lazy= V;
else{
if(E<=m)l->upd(S,E,V);
else if(S>m) r->upd(S,E,V);
else{
l-> upd(S,m,V);
r->upd(m+1,E,V);
}
l-> prop();
r->prop();
v=max(l->v, r->v);
}
}
int rmax(int S, int E){
prop();
//cout<<s<<' '<<e<<' '<<v<<endl;
if(s==S&&e==E){
return v;
}
if(E<=m)return l->rmax(S,E);
if(S>m) return r->rmax(S,E);
return max(l-> rmax(S,m), r->rmax(m+1,E));
}
}*rroot[20];// stores maxpos you can go from i using 1 train
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin>>n>>k>>m;
rep(j,18){
lroot[j-1]=new node(1,n+1);
rroot[j-1]=new nodee(1,n+1);
rep(i,n)lroot[j-1]->upd(i,i,i); //0 trains
rep(i,n)rroot[j-1]->upd(i,i,i);
}
//store value for 1 train
rep(i,m){
cin>>A>>B;
if(A>B){
//right to left, min
lroot[0]->upd(max(1,A-k+1),A,B);
}else{
// left to right, max
rroot[0]->upd(A,min(n, A+k-1), B);
//hopefully rroot is correct
}
}
//rep(i,n)cout<<lroot[0]->rmin(i,i)<<' ';cout<<endl;
//rep(i,n)cout<<rroot[0]->rmax(i,i)<<' ';cout<<endl;
rep(j,17){
rep(i,n){
int leftt=lroot[j-1]->rmin(i,i), rightt=rroot[j-1]->rmax(i,i);
lroot[j]->upd(i,i,lroot[j-1]->rmin(leftt,rightt));
rroot[j]->upd(i,i,rroot[j-1]->rmax(leftt,rightt));
}
//rep(i,n)cout<<lroot[0]->rmin(i,i)<<' ';cout<<endl;
//rep(i,n)cout<<rroot[0]->rmax(i,i)<<' ';cout<<endl;
}
cin>>q;
rep(loopp,q){
cin>>A>>B;
int ans=0, leftt=A, rightt=A, lef, rig;
//cout<<t[0][A][1]<<endl;
for(int i=17; i>=0; i--){
lef=lroot[i]->rmin(leftt, rightt);
rig=rroot[i]->rmax(leftt, rightt);
if (!(lef <= B && B <= rig)){
ans += (1<<i);
leftt=lef; rightt=rig;
}
}
lef=lroot[0]->rmin(leftt, rightt);
rig=rroot[0]->rmax(leftt, rightt);
if(lef <= B && B <= rig)cout<<ans+1<<'\n';
else cout<<-1<<'\n';
}
}
# | 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... |