oj.uz

Submission #580333

# Submission time Handle Problem Language Result Execution time Memory
580333 2022-06-21T05:50:35 Z 조영욱(#8357) Event Hopping (BOI22_events) C++17
20 / 100
 213 ms 12920 KB 
#include <bits/stdc++.h>
using namespace std;

int n,q;
typedef pair<int,int> P;
P arr[100000];
vector<int> pr;
const int sz=262144;
P seg[sz*2];
int table[100000][17];

P merge(P a,P b) {
    return a>b?a:b;
}

P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return P(-1,-1);
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return merge(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,P val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=merge(seg[i*2],seg[i*2+1]);
    }
}

int main(void) {
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) {
        scanf("%d %d",&arr[i].first,&arr[i].second);
        pr.push_back(arr[i].first);
        pr.push_back(arr[i].second);
    }
    sort(pr.begin(),pr.end());
    pr.erase(unique(pr.begin(),pr.end()),pr.end());
    for(int i=0;i<n;i++) {
        arr[i].first=lower_bound(pr.begin(),pr.end(),arr[i].first)-pr.begin();
        arr[i].second=lower_bound(pr.begin(),pr.end(),arr[i].second)-pr.begin();
        //printf("%d %d\n",arr[i].first,arr[i].second);
        update(arr[i].first,P(arr[i].second,i));
    }
    memset(table,-1,sizeof(table));
    for(int i=0;i<n;i++) {
        P val=sum(0,arr[i].second);
        //printf("%d %d\n",val.first,val.second);
        if (val.first>arr[i].second) {
            table[i][0]=val.second;
        }
        //printf("%d.\n",table[i][0]);
    }
    for(int j=1;j<17;j++) {
        for(int i=0;i<n;i++) {
            if (table[i][j-1]!=-1) {
                table[i][j]=table[table[i][j-1]][j-1];
            }
        }
    }
    for(int i=0;i<q;i++) {
        int s,e;
        scanf("%d %d",&s,&e);
        s--;
        e--;
        if (s==e) {
            printf("0\n");
            continue;
        }
        if (arr[e].second<arr[s].second) {
            printf("impossible\n");
            continue;
        }
        if (arr[e].first<=arr[s].second) {
            printf("1\n");
            continue;
        }
        int now=s;
        int ret=0;
        for(int j=16;j>=0;j--) {
            int nt=table[now][j];
            if (nt!=-1&&arr[nt].second<arr[e].first) {
                ret+=(1<<j);
                now=nt;
            }
        }
        int nt=table[now][0];
        if (nt==-1||arr[nt].second<arr[e].first) {
            printf("impossible\n");
            continue;
        }
        printf("%d\n",ret+2);
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
events.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d %d",&arr[i].first,&arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d",&s,&e);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Incorrect 3 ms 6996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Incorrect 3 ms 6996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6996 KB Output is correct
2 Incorrect 3 ms 6996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 10840 KB Output is correct
2 Correct 151 ms 10816 KB Output is correct
3 Correct 209 ms 10824 KB Output is correct
4 Correct 158 ms 12920 KB Output is correct
5 Correct 209 ms 11460 KB Output is correct
6 Correct 173 ms 12800 KB Output is correct
7 Correct 213 ms 12900 KB Output is correct
8 Correct 145 ms 12840 KB Output is correct
9 Correct 107 ms 10428 KB Output is correct
10 Correct 176 ms 12908 KB Output is correct
11 Correct 150 ms 12192 KB Output is correct
12 Correct 173 ms 12400 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -