제출 #745185

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
745185	2023-05-19 14:20:07	sword060	Osumnjičeni (COCI21_osumnjiceni)	C++17	30 / 110	131 ms	2208 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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5,M=18;
int x,q,l[N],r[N],nxt[N][20];
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>x;
  for(int i=1;i<=x;i++)cin>>l[i]>>r[i];
  for(int j=0;j<=M;j++)nxt[x+1][j]=x+1;
  for(int i=x;i>=1;i--){
    nxt[i][0]=(i<x?nxt[i+1][0]:i+1);
    for(int j=x;j>i;j--)
      if(max(l[i],l[j])<=min(r[i],r[j]))
        nxt[i][0]=min(nxt[i][0],j);
    for(int j=1;j<=M;j++)
      nxt[i][j]=nxt[nxt[i][j-1]][j-1];
  }
  cin>>q;
  while(q--){
    int c1,c2,ans=1;cin>>c1>>c2;
    for(int i=M;i>=0;i--)
      if(nxt[c1][i]<=c2)
        c1=nxt[c1][i],ans+=(1<<i);
    cout<<ans<<"\n";
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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