oj.uz

Submission #579966

# Submission time Handle Problem Language Result Execution time Memory
579966 2022-06-20T12:01:05 Z haojiandan Event Hopping (BOI22_events) C++14
30 / 100
 334 ms 22532 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 191 ms 20200 KB Output is correct
3 Correct 178 ms 20152 KB Output is correct
4 Correct 240 ms 20280 KB Output is correct
5 Correct 192 ms 20704 KB Output is correct
6 Correct 187 ms 20784 KB Output is correct
7 Correct 251 ms 20784 KB Output is correct
8 Correct 167 ms 18804 KB Output is correct
9 Correct 159 ms 18912 KB Output is correct
10 Correct 189 ms 20076 KB Output is correct
11 Correct 190 ms 22376 KB Output is correct
12 Correct 120 ms 16520 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 20092 KB Output is correct
2 Correct 192 ms 20132 KB Output is correct
3 Correct 264 ms 20192 KB Output is correct
4 Correct 160 ms 18836 KB Output is correct
5 Correct 183 ms 20196 KB Output is correct
6 Correct 243 ms 22372 KB Output is correct
7 Correct 251 ms 22332 KB Output is correct
8 Correct 271 ms 22508 KB Output is correct
9 Correct 231 ms 15312 KB Output is correct
10 Correct 240 ms 22532 KB Output is correct
11 Correct 334 ms 21004 KB Output is correct
12 Correct 234 ms 22340 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 191 ms 20200 KB Output is correct
3 Correct 178 ms 20152 KB Output is correct
4 Correct 240 ms 20280 KB Output is correct
5 Correct 192 ms 20704 KB Output is correct
6 Correct 187 ms 20784 KB Output is correct
7 Correct 251 ms 20784 KB Output is correct
8 Correct 167 ms 18804 KB Output is correct
9 Correct 159 ms 18912 KB Output is correct
10 Correct 189 ms 20076 KB Output is correct
11 Correct 190 ms 22376 KB Output is correct
12 Correct 120 ms 16520 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 4 ms 468 KB Output is correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Halted 0 ms 0 KB -