Submission #579994

#	Time	Username	Problem	Language	Result	Execution time	Memory
579994		haojiandan	Event Hopping (BOI22_events)	C++14	100 / 100	234 ms	19276 KiB

events

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
    t=0; char ch=getchar(); int f=1;
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
    if (t<0) { putchar('-'); write(-t); return; }
    if (t>9) write(t/10);
    putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const int maxn=(2e5)+10;
int n,q,tot;
struct node {
    int x,y,z,id;
} Q[maxn],d[maxn];
bool cmp(node A,node B) { return A.x<B.x; }
int ans[maxn];
int lsh[maxn],bad[maxn];
int tr[maxn*4],lazy[maxn*4];
int MN(int a,int b) { if (a==n+1) return b; if (b==n+1) return a; if (d[a].x<d[b].x) return a; return b; }
void puttag(int root,int delta) {
    lazy[root]=MN(lazy[root],delta);
    tr[root]=MN(tr[root],delta);
}
void pushdown(int root) {
    puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]),lazy[root]=n+1;
}
void add(int x,int l,int r,int root,int delta) {
    if (l==r) { puttag(root,delta); return; }
    int mid=(l+r)>>1; pushdown(root);
    if (x<=mid) add(x,l,mid,root<<1,delta);
    else add(x,mid+1,r,root<<1|1,delta);
    tr[root]=MN(tr[root<<1],tr[root<<1|1]);
}
int rem[maxn],f[maxn][20],N;
int query(int L,int R,int l,int r,int root) {
    if (L<=l&&r<=R) return tr[root];
    int mid=(l+r)>>1,res=n+1; pushdown(root);
    if (L<=mid) res=MN(res,query(L,R,l,mid,root<<1));
    if (mid<R) res=MN(res,query(L,R,mid+1,r,root<<1|1));
    return res;
}
int main() {
    //freopen("1.txt","r",stdin);
    read(n),read(q);
    for (int i=1;i<=n;i++) read(d[i].x),read(d[i].y),lsh[++N]=d[i].x,lsh[++N]=d[i].y;
    sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
    for (int i=1;i<=N*4;i++) tr[i]=lazy[i]=n+1;
    for (int i=1;i<=n;i++) {
        int r=lower_bound(lsh+1,lsh+N+1,d[i].y)-lsh;
        add(r,1,N,1,i);
    }
    for (int i=1;i<=n;i++) {
        int l=lower_bound(lsh+1,lsh+N+1,d[i].x)-lsh;
        int r=lower_bound(lsh+1,lsh+N+1,d[i].y)-lsh;
        f[i][0]=query(l,r,1,N,1);
    //    printf("i=%d,f=%d\n",i,f[i][0]);
    }
    for (int i=1;i<=19;i++)
    for (int j=1;j<=n;j++)
        f[j][i]=f[f[j][i-1]][i-1];
    for (int i=1;i<=q;i++) {
        int x,y;
        read(x),read(y);
        if (x==y) { puts("0"); continue; }
        if (d[x].y>=d[y].x&&d[x].y<=d[y].y) { puts("1"); continue; }
        for (int j=19;j>=0;j--)
            if (d[f[y][j]].x>d[x].y) y=f[y][j],ans[i]+=1<<j;
        if (d[y].x>d[x].y) y=f[y][0],ans[i]++;
        //printf(" %d\n",y);
        if (d[x].y>=d[y].x&&d[x].y<=d[y].y) printf("%d\n",ans[i]+(x!=y));
        else puts("impossible");
    }
    return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
 
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
   
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
   
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30