Submission #705629

#	Time	Username	Problem	Language	Result	Execution time	Memory
705629		Username4132	Osumnjičeni (COCI21_osumnjiceni)	C++14	110 / 110	388 ms	42216 KiB

Main

#include<iostream>
#include<set>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define F first
#define S second

const int MAXN=200010;
int n, q, l[MAXN], r[MAXN], up[20][MAXN], lo=0;

set<pii> s;

bool test(int ld, int rd){
    auto itrl=s.lower_bound({ld, -2}), itrr=s.upper_bound({rd, 1100000000});
    return (itrl->F==itrr->F) && (itrr==s.end() || itrr->S < n);
}

int main(){
    scanf("%d", &n);
    forn(i, n){
        scanf("%d %d", l+i, r+i);
        while(!test(l[i], r[i])){
            s.erase({l[lo], lo});
            s.erase({r[lo], n+lo});
            up[0][lo++]=i;
        }
        s.insert({l[i], i});
        s.insert({r[i], n+i});
    }
    while(lo<=n) up[0][lo++]=n;
    forn(i, 19) forn(j, n+1) up[i+1][j]=up[i][up[i][j]];
    scanf("%d", &q);
    forn(qnum, q){
        int a, b, ans=1; scanf("%d %d", &a, &b); --a;
        dforn(i, 20) if(up[i][a]<b) a=up[i][a], ans+=(1<<i);
        printf("%d\n", ans);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d %d", l+i, r+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         int a, b, ans=1; scanf("%d %d", &a, &b); --a;
      |                          ~~~~~^~~~~~~~~~~~~~~~~

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