oj.uz

Submission #714233

# Submission time Handle Problem Language Result Execution time Memory
714233 2023-03-24T06:50:38 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 71756 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);
    for(int i=1;i<=n;i++){
        cin >> a[i] >> b[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                continue;
            }
            if(a[i]<=b[j] && b[j]<=b[i]){
                g[j].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 12076 KB Output is correct
2 Execution timed out 1584 ms 13784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12076 KB Output is correct
2 Correct 7 ms 12076 KB Output is correct
3 Correct 17 ms 12140 KB Output is correct
4 Correct 16 ms 12144 KB Output is correct
5 Correct 16 ms 12116 KB Output is correct
6 Correct 22 ms 13976 KB Output is correct
7 Correct 39 ms 15692 KB Output is correct
8 Correct 48 ms 17660 KB Output is correct
9 Correct 128 ms 20268 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12076 KB Output is correct
2 Correct 7 ms 12076 KB Output is correct
3 Correct 17 ms 12140 KB Output is correct
4 Correct 16 ms 12144 KB Output is correct
5 Correct 16 ms 12116 KB Output is correct
6 Correct 22 ms 13976 KB Output is correct
7 Correct 39 ms 15692 KB Output is correct
8 Correct 48 ms 17660 KB Output is correct
9 Correct 128 ms 20268 KB Output is correct
10 Correct 6 ms 12076 KB Output is correct
11 Correct 8 ms 12088 KB Output is correct
12 Correct 18 ms 12116 KB Output is correct
13 Correct 16 ms 12096 KB Output is correct
14 Correct 17 ms 12116 KB Output is correct
15 Correct 21 ms 13976 KB Output is correct
16 Correct 35 ms 15700 KB Output is correct
17 Correct 35 ms 17620 KB Output is correct
18 Correct 133 ms 20220 KB Output is correct
19 Execution timed out 1573 ms 71756 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12076 KB Output is correct
2 Correct 7 ms 12076 KB Output is correct
3 Correct 17 ms 12140 KB Output is correct
4 Correct 16 ms 12144 KB Output is correct
5 Correct 16 ms 12116 KB Output is correct
6 Correct 22 ms 13976 KB Output is correct
7 Correct 39 ms 15692 KB Output is correct
8 Correct 48 ms 17660 KB Output is correct
9 Correct 128 ms 20268 KB Output is correct
10 Correct 7 ms 12076 KB Output is correct
11 Correct 6 ms 12076 KB Output is correct
12 Correct 18 ms 12168 KB Output is correct
13 Correct 19 ms 12116 KB Output is correct
14 Correct 18 ms 12116 KB Output is correct
15 Correct 25 ms 13952 KB Output is correct
16 Correct 39 ms 15700 KB Output is correct
17 Correct 44 ms 17620 KB Output is correct
18 Correct 157 ms 20268 KB Output is correct
19 Execution timed out 1591 ms 13852 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1564 ms 13988 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 12076 KB Output is correct
2 Execution timed out 1584 ms 13784 KB Time limit exceeded
3 Halted 0 ms 0 KB -