Submission #579966

#	Time	Username	Problem	Language	Result	Execution time	Memory
579966		haojiandan	Event Hopping (BOI22_events)	C++14	30 / 100	334 ms	22532 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 MX(int a,int b) { if (!a||!b) return a+b; if (d[a].y>d[b].y) return a; return b; }
void puttag(int root,int delta) {
    lazy[root]=MX(lazy[root],delta);
    tr[root]=MX(tr[root],delta);
}
void pushdown(int root) {
    puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]),lazy[root]=0;
}
void add(int L,int R,int l,int r,int root,int delta) {
    if (L<=l&&r<=R) { puttag(root,delta); return; }
    int mid=(l+r)>>1; pushdown(root);
    if (L<=mid) add(L,R,l,mid,root<<1,delta);
    if (mid<R) add(L,R,mid+1,r,root<<1|1,delta);
    tr[root]=MX(tr[root<<1],tr[root<<1|1]);
}
int rem[maxn],f[maxn][20],N;
void dfs(int l,int r,int root) {
    if (l==r) { rem[l]=tr[root]; return; }
    int mid=(l+r)>>1; pushdown(root);
    dfs(l,mid,root<<1),dfs(mid+1,r,root<<1|1);
}
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;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;
        add(l,r,1,N,1,i);
    }
    dfs(1,N,1);
    for (int i=1;i<=n;i++) {
        int r=lower_bound(lsh+1,lsh+N+1,d[i].y)-lsh;
        f[i][0]=rem[r];
    //    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) continue;
        if (d[x].y>=d[y].x&&d[x].y<=d[y].y) { ans[i]=1; continue; }
        for (int j=19;j>=0;j--)
            if (d[f[x][j]].y<d[y].x) x=f[x][j],ans[i]+=1<<j;
        ans[i]+=2;
        if (d[x].y>d[y].x) bad[i]=1;
        else Q[++tot]=(node){d[x].y,d[y].x,d[y].y,i};
//        if (i==3) printf("? %d %d\n",d[x].y,d[y].x);
    }
    sort(Q+1,Q+tot+1,cmp);
    sort(d+1,d+n+1,cmp);
    int pos=1; set<int> s;
    for (int i=1;i<=tot;i++) {
        while (pos<=n&&d[pos].x<=Q[i].x) {
            s.insert(d[pos].y); pos++;
        }
        set<int>::iterator it=s.lower_bound(Q[i].y);
        if (it!=s.end()&&(*it)<=Q[i].z); else bad[Q[i].id]=1;
    }
    for (int i=1;i<=q;i++) {
        if (bad[i]) puts("impossible");
        else printf("%d\n",ans[i]);
    }
    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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30