Submission #1237477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237477		lkateris	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	344 ms	22320 KiB

Main

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;

int N;
pair<int,int> h[200005];
int cnt;

int seg[800020];
int lazy[800020];

map<int,int> M;

void push(int ind) {
    if (lazy[ind] != 0) {
        lazy[ind*2] = max(lazy[ind*2], lazy[ind]);
        lazy[ind*2+1] = max(lazy[ind*2+1], lazy[ind]);
        seg[ind*2] = max(seg[ind*2], lazy[ind]);
        seg[ind*2+1] = max(seg[ind*2+1], lazy[ind]);
        lazy[ind] = 0;
    }
}

void Update(int from, int to, int val, int start=1, int ende=cnt, int ind=1) {

    if (from == start and ende == to) {
        seg[ind] = max(seg[ind], val);
        lazy[ind] = max(lazy[ind], val);
        return;
    }

    push(ind);
    int mid = (start + ende) / 2;

    Update(from, to, val, start, mid, ind*2);
    Update(from, to, val, mid+1, ende, ind*2+1);

    seg[ind] = max(seg[ind*2], seg[ind*2+1]);
}

int Query(int from, int to, int start=1, int ende=cnt, int ind=1) {


    if (from == start and ende == to) return seg[ind];

    push(ind);
    int mid = (start + ende) / 2;

    int leftMax = Query(from, to, start, mid, ind*2);
    int rightMax = Query(from, to, mid+1, ende, ind*2+1);
    if (leftMax > rightMax) return leftMax;
    else return rightMax;
}

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}

int main() {
    scanf("%d", &N);

    vector<int> V;
    for (int i = 1; i <= N; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        h[i] = make_pair(l, r);
        V.push_back(l);
        V.push_back(r);
    }

    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());

    cnt = (int)V.size();

    for (int i = 0; i < cnt; i++) {
        M[V[i]] = i + 1;
    }

    for (int i = 1; i <= N; i++) {
        int l = M[h[i].first];
        int r = M[h[i].second];
        h[i] = make_pair(l, r);
    }

    int s = 1;
    vector<pair<int,int>> ranges;

    for (int i = 1; i <= N; i++) {
        int l = h[i].first;
        int r = h[i].second;

        int q = Query(l, r);
        if (q >= s) {
            ranges.push_back(make_pair(s, i - 1));
            s = q + 1;
        }
        Update(l, r, i);
    }
    if (s <= N) ranges.push_back(make_pair(s, N));
    sort(ranges.begin(), ranges.end());

    int Q;
    scanf("%d", &Q);

    while (Q--) {
        int a, b;
        scanf("%d %d", &a, &b);

        int l = (lower_bound(ranges.begin(), ranges.end(), make_pair(a, INT_MAX)) - ranges.begin());
        if (l > 0) l--;
        else l = -1;

        int r = (lower_bound(ranges.begin(), ranges.end(), make_pair(0, b), cmp) - ranges.begin());

        int ans = r - l+1;
        if (ans < 0) ans = 0;

        printf("%d\n", ans);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50