Submission #855892

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
855892	2023-10-02 07:06:20	NotLinux	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	420 ms	33668 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>
using namespace std;
void solve(){
  int n;cin >> n;
  int l[n],r[n],lift[n+1][21];
  lift[n][0] = n;
  for(int i = 0;i<n;i++)cin >> l[i] >> r[i];
  set < pair < int , int > > ste;
  int rp = 0;
  for(int lp = 0;lp < n;lp++){
    while(rp != n){
      //cout << lp << " : ";for(auto itr : ste)cout << itr.first << "," << itr.second << "   ";cout << endl;
      if(ste.size() == 0){
      //  cout << "added " << lp << " " << rp << endl;
        ste.insert({l[rp],r[rp]});
        rp++;
      }
      else{
        auto it = ste.lower_bound(make_pair(l[rp],1e9 + 7));
        pair < int , int > cand1 , cand2;
        if(it == ste.end())cand2 = {-1,-1};
        else cand2 = *it;
        if(it == ste.begin())cand1 = {-1,-1};
        else cand1 = *(--it);
      //  cout << "trying : " << lp << " " << rp << " " << cand1.first << " " << cand1.second << " : " << cand2.first << " " << cand2.second << endl;
        if((cand1.first > r[rp] or cand1.second < l[rp]) and (cand2.first > r[rp] or cand2.second < l[rp])){
          ste.insert({l[rp],r[rp]});
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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