oj.uz

Submission #1112746

# Submission time Handle Problem Language Result Execution time Memory
1112746 2024-11-14T18:24:17 Z cpptowin Event Hopping (BOI22_events) C++17
20 / 100
 200 ms 137408 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if(x < 0) x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if(x < 0) x += mod;
}
int n,q;
array<int,3> a[maxn];
pii rmq[maxn][20];
pii minn[maxn][20];
vi nen;
pii getmin(int l,int r) 
{
    int lg = __lg(r - l + 1);
    return min(minn[l][lg],minn[r - (1 << lg) + 1][lg]);
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    fo(i,1,n) 
    {
        cin >> a[i][0] >> a[i][1];
        nen.pb(a[i][0]);
        nen.pb(a[i][1]);
        a[i][2] = i;
    }
    sort(all(nen));UNIQUE(nen);
    fo(i,1,ss(nen)) fo(j,0,19) minn[i][j] = rmq[i][j] = {inf,inf};
    fo(i,1,n) 
    {
        a[i][0] = lower_bound(all(nen),a[i][0]) - nen.begin() + 1;
        a[i][1] = lower_bound(all(nen),a[i][1]) - nen.begin() + 1;
        minimize(minn[a[i][1]][0],make_pair(a[i][0],i));
    }
    fo(j,1,19) fo(i,1,ss(nen)) 
        minn[i][j] = min(minn[i][j - 1],minn[i + (1 << j - 1)][j - 1]);
    fo(i,1,n) 
    {
        rmq[i][0] = getmin(a[i][0],ss(nen));
    }
    // cout << rmq[8][0].fi << ' ' << rmq[8][0].se;en;
    fo(j,1,19) fo(i,1,n) 
    {
        if(rmq[i][j - 1].fi == inf) continue;
        rmq[i][j] = rmq[rmq[i][j - 1].se][j - 1];
    }
    while(q--) 
    {
        int l,r;
        cin >> l >> r;
        if(a[r][1] < a[l][0]) 
        {
            cout << "impossible";en;
            continue;
        }
        if(l == r) 
        {
            cout << 0;en;
            continue;
        }
        if(a[r][0] <= a[l][1] and a[l][1] <= a[r][1])
        {
            cout << 1;en;
            continue;
        }
        int ans = 0;
        fod(i,19,0) if(rmq[r][i].fi != inf and rmq[r][i].fi > a[l][1]) 
        {
            ans += (1 << i);
            r = rmq[r][i].se;
            if(r == inf) break;
        }
        // cout << r;en;
        if(r != inf) 
        {
            r = rmq[r][0].se;
            ans++;
            if(r != inf and a[r][0] <= a[l][1] and a[r][1] >= a[l][1]) 
            {
                cout << ans + 1;en;
                continue;
            }
            else cout << "impossible \n";
        }
        else cout << "impossible\n";
    }
}

Compilation message

events.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main()
      | ^~~~
events.cpp: In function 'int main()':
events.cpp:95:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |         minn[i][j] = min(minn[i][j - 1],minn[i + (1 << j - 1)][j - 1]);
      |                                                        ~~^~~
events.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Incorrect 1 ms 4600 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 109 ms 71104 KB Output is correct
2 Correct 130 ms 71116 KB Output is correct
3 Correct 178 ms 71008 KB Output is correct
4 Correct 169 ms 137408 KB Output is correct
5 Correct 134 ms 74580 KB Output is correct
6 Correct 200 ms 137152 KB Output is correct
7 Correct 200 ms 136896 KB Output is correct
8 Correct 181 ms 137148 KB Output is correct
9 Correct 148 ms 134992 KB Output is correct
10 Correct 183 ms 136640 KB Output is correct
11 Correct 172 ms 136272 KB Output is correct
12 Correct 189 ms 136640 KB Output is correct

Subtask #6
0 / 30.0

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