제출 #720677

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
720677	2023-04-08 23:32:56	Yell0	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	318 ms	32852 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int,int> pii;
const int MN=4e5+5,LOG=20;
int N,Q,st[LOG][MN];
pii a[MN];
set<pii> s;
bool chk(int i) {
    if(s.empty()) return 1;
    auto nxt=s.lower_bound(a[i]);
    if(a[i].f<=nxt->f&&nxt->f<=a[i].s) return 0;
    if(nxt!=s.begin()) {
        nxt--;
        if(nxt->f<=a[i].f&&a[i].f<=nxt->s) return 0;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++) cin>>a[i].f>>a[i].s;
    for(int l=1,r=1;l<=N;l++) {
        while(r<=N&&chk(r)) {s.insert(a[r]);r++;}
        st[0][l]=r;
        s.erase(a[l]);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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