oj.uz

Submission #714248

# Submission time Handle Problem Language Result Execution time Memory
714248 2023-03-24T07:02:00 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 487220 KB 
#include <bits/stdc++.h>
#define MAX 300001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,cnt=0,a[MAX],b[MAX],d[MAX],d2[MAX],resa[MAX],x,y,z,x2,y2,z2,res1=0,cnt1,cnt2,cnt3;
ll c[501][501];
ll fact[MAX];
ll inv_fact[MAX];
//char c;
string str[MAX];
string s1,s2;
vector<tuple<ll,ll,ll>> v;
vector<pll> v1,v2,v3,v4;
const int mod = 998244353;
ll modmul(ll x,ll y,ll md){
    if(y==1){
        return x;
    }
    if(y%2){
        return (x+modmul(x,y-1,md))%md;
    }
    else{
        return (modmul((x+x)%md,y/2,md))%md;
    }
}
ll powmod(ll x,ll y,ll md){
    x%=md;
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y){
        if(y%2==1){
            res*=x;
            res%=md;
        }
        x*=x;
        x%=md;
        y/=2;
    }
    return res;
}
ll pow2(ll x,ll y){
    if(x==0){
        return 0;
    }
    ll res=1;
    while(y>0){
        if(y%2==1){
            if(res>=1e18/x){
                res=1e18;
            }
            else{
                res*=x;
            }
        }
        if(x>=1e18/x){
            x=1e18;
        }
        else{
            x*=x;
        }
        y/=2;
    }
    return res;
}
ll inv(ll n,ll md){
    return powmod(n,md-2,md);
}
ll nCkm(ll n,ll k,ll md){
    if(n-k<0){
        return 0;
    }
    return fact[n]*inv_fact[k]%md*inv_fact[n-k]%md;
}
ll nCk(ll x,ll y){
    if(x<y){
        return 0;
    }
    ll res=1;
    if(y>x-y){
        for(int i=y+1;i<=x;i++){
            res*=i;
        }
        for(int i=2;i<=x-y;i++){
            res/=i;
        }
    }
    else{
        for(int i=x-y+1;i<=x;i++){
            res*=i;
        }
        for(int i=2;i<=y;i++){
            res/=i;
        }
    }
    return res;
}
ll countbits(ll x){
    ll cnt=0;
    while(x){
        cnt+=x&1;
        x>>=1;
    }
    return cnt;
}
ll gcd(ll x,ll y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}
ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
}
bool alpha(char c1,char c2){
    ll h1,h2;
    if(c1>='a'){
        h1=c1-'a';
    }
    else{
        h1=c1-'A';
    }
    if(c2>='a'){
        h2=c2-'a';
    }
    else{
        h2=c2-'A';
    }
    if(h1==h2){
        return c1<c2;
    }
    else{
        return h1<h2;
    }
}
ll dx[4]={1,0,0,-1};
ll dy[4]={0,1,-1,0};
struct custom_hash {
   static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
struct segtree{
    int size;
    vector<ll> minimum;
    void build(vector<int> &a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                minimum[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        minimum[x]=min(minimum[2*x+1],minimum[2*x+2]);
    }
    void build(vector<int> &a){
        build(a,0,0,size);
    }
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        minimum.assign(2*size,INF);
    }
    ll get_min(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l){
            return INF;
        }
        if(lx>=l && rx<=r){
            return minimum[x];
        }
        ll s1,s2;
        int m=(lx+rx)/2;
        s1=get_min(l,r,2*x+1,lx,m);
        s2=get_min(l,r,2*x+2,m,rx);
        return min(s1,s2);
    }
    ll get_min(int l,int r){
        return get_min(l,r,0,0,size);
    }
    void set(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            minimum[x]=v;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m);
        }
        else{
            set(i,v,2*x+2,m,rx);
        }
        minimum[x]=min(minimum[2*x+1],minimum[2*x+2]);
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
};
struct segtree2{
    int size;
    vector<ll> maximum;
    void build(vector<int> &a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                maximum[x]=a[lx];
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        maximum[x]=max(maximum[2*x+1],maximum[2*x+2]);
    }
    void build(vector<int> &a){
        build(a,0,0,size);
    }
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        maximum.assign(2*size,-INF);
    }
    ll get_max(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l){
            return -INF;
        }
        if(lx>=l && rx<=r){
            return maximum[x];
        }
        ll s1,s2;
        int m=(lx+rx)/2;
        s1=get_max(l,r,2*x+1,lx,m);
        s2=get_max(l,r,2*x+2,m,rx);
        return max(s1,s2);
    }
    ll get_max(int l,int r){
        return get_max(l,r,0,0,size);
    }
    void set(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            maximum[x]=v;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m);
        }
        else{
            set(i,v,2*x+2,m,rx);
        }
        maximum[x]=max(maximum[2*x+1],maximum[2*x+2]);
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
};
vector<vector<ll>> g;
ll bfs(ll s,ll e){
    vector<ll> dist(MAX,-1);
    queue<ll> q;
    q.push(s);
    dist[s]=0;
    while(!q.empty()){
        ll v=q.front();
        q.pop();
        for(auto x:g[v]){
            if(dist[x]==-1){
                dist[x]=dist[v]+1;
                q.push(x);
            }
        }
    }
    return dist[e];
}
void solve(){
    cin >> n >> q;
    g.resize(n+1);
    vector<pll> c;
    vector<ll> d;
    for(int i=1;i<=n;i++){
        cin >> a[i] >> b[i];
        c.pb(mp(b[i],i));
        d.pb(b[i]);
    }
    sortv(c);
    sortv(d);
    for(int i=1;i<=n;i++){
        ll ind1,ind2;
        ind1=lb(d,a[i])-d.begin();
        ind2=ub(d,b[i])-d.begin();
        for(int j=ind1;j<ind2;j++){
            if(c[j].ss==i){
                continue;
            }
            g[c[j].ss].pb(i);
        }
    }
    for(int i=0;i<q;i++){
        cin >> x >> y;
        ll h=bfs(x,y);
        if(h==-1){
            cout << "impossible" << "\n";
        }
        else{
            cout << h << "\n";
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //USACO("poetry");
    //freopen("input.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++;
    }
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12092 KB Output is correct
2 Execution timed out 1591 ms 21456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12076 KB Output is correct
2 Correct 6 ms 12076 KB Output is correct
3 Correct 14 ms 12208 KB Output is correct
4 Correct 12 ms 12212 KB Output is correct
5 Correct 13 ms 12204 KB Output is correct
6 Correct 20 ms 13908 KB Output is correct
7 Correct 31 ms 15624 KB Output is correct
8 Correct 37 ms 17592 KB Output is correct
9 Correct 131 ms 20268 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12076 KB Output is correct
2 Correct 6 ms 12076 KB Output is correct
3 Correct 14 ms 12208 KB Output is correct
4 Correct 12 ms 12212 KB Output is correct
5 Correct 13 ms 12204 KB Output is correct
6 Correct 20 ms 13908 KB Output is correct
7 Correct 31 ms 15624 KB Output is correct
8 Correct 37 ms 17592 KB Output is correct
9 Correct 131 ms 20268 KB Output is correct
10 Correct 7 ms 12096 KB Output is correct
11 Correct 7 ms 12076 KB Output is correct
12 Correct 16 ms 12208 KB Output is correct
13 Correct 12 ms 12204 KB Output is correct
14 Correct 15 ms 12204 KB Output is correct
15 Correct 21 ms 13908 KB Output is correct
16 Correct 32 ms 15660 KB Output is correct
17 Correct 36 ms 17672 KB Output is correct
18 Correct 130 ms 20280 KB Output is correct
19 Execution timed out 1587 ms 71552 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12076 KB Output is correct
2 Correct 6 ms 12076 KB Output is correct
3 Correct 14 ms 12208 KB Output is correct
4 Correct 12 ms 12212 KB Output is correct
5 Correct 13 ms 12204 KB Output is correct
6 Correct 20 ms 13908 KB Output is correct
7 Correct 31 ms 15624 KB Output is correct
8 Correct 37 ms 17592 KB Output is correct
9 Correct 131 ms 20268 KB Output is correct
10 Correct 7 ms 12076 KB Output is correct
11 Correct 7 ms 12076 KB Output is correct
12 Correct 14 ms 12216 KB Output is correct
13 Correct 13 ms 12204 KB Output is correct
14 Correct 14 ms 12188 KB Output is correct
15 Correct 19 ms 13924 KB Output is correct
16 Correct 32 ms 15780 KB Output is correct
17 Correct 39 ms 17620 KB Output is correct
18 Correct 128 ms 20372 KB Output is correct
19 Correct 903 ms 21464 KB Output is correct
20 Correct 491 ms 28160 KB Output is correct
21 Execution timed out 1548 ms 487220 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 21544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12092 KB Output is correct
2 Execution timed out 1591 ms 21456 KB Time limit exceeded
3 Halted 0 ms 0 KB -