Submission #1237484

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

Main

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

using namespace std;

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

int seg[2000040];
int lazy[2000040];

map<int,int> M;

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

    int mid = (start+ende)/2;

    if (lazy[ind]) {
        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;
    }

    if (to <= mid) Update(from,to,val,start,mid,ind*2);
    else if (mid < from) Update(from,to,val,mid+1,ende,ind*2 + 1);
    else {
        Update(from,mid,val,start,mid,ind*2);
        Update(mid+1,to,val,mid+1,ende,ind*2 + 1);
    }
    seg[ind] = max(seg[ind*2],seg[ind*2 + 1]);
    return;
}

int Query(int from,int to,int start=1,int ende=cnt,int ind=1) {
    if (start == from and ende == to) {
        return seg[ind];
    }

    int mid = (start+ende)/2;

    if (lazy[ind]) {
        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;
    }

    if (to <= mid) return Query(from,to,start,mid,ind*2);
    else if (mid < from) return Query(from,to,mid+1,ende,ind*2 + 1);
    else return max( Query(from,mid,start,mid,ind*2), Query(mid+1,to,mid+1,ende,ind*2 + 1));
}

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());


    for(int i=0;i<2*N;++i) {
        if (i != 0 and V[i] == V[i-1]) continue;
        M[V[i]] = cnt;
        cnt++;
    }
    cnt--;
    for(int i=1;i<=N;++i) {
        int k1 = M[h[i].first];
        int k2 = M[h[i].second];
        if (k1 > k2) swap(k1,k2);
        h[i] = make_pair(k1,k2);
    }
    int s = 1;

    vector<pair<int,int> > ranges;

    for(int i=1;i<=N;++i) {
        int l=h[i].first,r=h[i].second;
        if (l > r) swap(l,r);
        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);

    for(int i=0;i<Q;++i) {
        int a,b;
        scanf("%d%d",&a,&b);

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

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

        printf("%d\n",r-l+1);
    }


    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
Main.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d %d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
Main.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         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