Submission #1237445

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

Main

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

using namespace std;

int N;
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=N,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 (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=N,int ind=1) {
    if (start == from and ende == to) {
        return seg[ind];
    }

    int mid = (start+ende)/2;

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

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

    int cnt = 1;
    for(int i=0;i<2*N;++i) {
        if (i != 0 and V[i] == V[i-1]) continue;
        M[V[i]] = 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(q,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();
        l--;
        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:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
Main.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d %d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
Main.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         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