oj.uz

Submission #531816

# Submission time Handle Problem Language Result Execution time Memory
531816 2022-03-01T15:25:35 Z Killer2501 Osumnjičeni (COCI21_osumnjiceni) C++14
0 / 110
 105 ms 23688 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<ll, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const ll inf = 1e16;
int n, lab[N], t, c[N], h[N], P[N][20], m, a[N], b[N], ans, d[N], k;
vector<int> adj[N];
vector<int> vi;
string s;
bool vis[N];
void add(int& x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
}
int findp(int u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(int u, int v)
{
    u = findp(u);
    v = findp(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}
pii p[N];
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> p[i].fi >> p[i].se;
    multiset<int> l, r;
    for(int i = 1, j = 1; i <= n; i ++)
    {
        while(j <= n)
        {
            auto it = l.lower_bound(p[j].fi);
            if(it != l.end() && (*it) <= p[j].se)break;
            it = r.upper_bound(p[j].se);
            if(it != r.begin())
            {
                --it;
                if((*it) >= p[j].fi)break;
            }
            l.insert(p[j].fi);
            r.insert(p[j].se);
            ++j;
        }
        l.erase(l.find(p[i].fi));
        r.erase(r.find(p[i].se));
        P[i][0] = j;
        //cout << i <<" "<<j<<'\n';
    }
    P[n][0] = n+1;
    for(int j = 1; j <= 18; j ++)
    {
        for(int i = 1; i <= n; i ++)
        {
            P[i][j] = P[P[i][j-1]][j-1];
        }
    }

    cin >> m;
    while(m -- > 0)
    {
        int l, r;
        cin >> l >> r;
        ans = 1;
        for(int j = 18; j >= 0; j --)
        {
            if(P[l][j] && P[l][j] <= r)
            {
                ans += (1<<j);
                l = P[l][j];
            }
        }
        cout << ans << '\n';

    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}
/*
1234
21
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 50.0

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