Submission #580724

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
580724	2022-06-21 17:27:55	penguinhacker	Event Hopping (BOI22_events)	C++17	100 / 100	191 ms	25276 KiB

events

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;
#define ll long long
#define ar array
const int mxN=1e5;
int n, q, lg[2*mxN+1], st[2*mxN][18], lift[mxN][17];
ar<int, 2> events[mxN];
vector<int> d;
int cmb(int a, int b) {
  if (a==-1||b==-1)
    return a==-1?b:a;
  return events[a][0]<events[b][0]?a:b;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i=0; i<n; ++i) {
    cin >> events[i][0] >> events[i][1];
    d.push_back(events[i][0]);
    d.push_back(events[i][1]);
  }
  sort(d.begin(), d.end());
  d.resize(unique(d.begin(), d.end())-d.begin());
  memset(st, -1, sizeof(st));
  for (int i=0; i<n; ++i) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i=2; i<=d.size(); ++i)
      |                ~^~~~~~~~~~
events.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int j=1; (1<<j)<=d.size(); ++j)
      |                ~~~~~~^~~~~~~~~~
events.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i=0; i+(1<<j)-1<d.size(); ++i)
      |                 ~~~~~~~~~~^~~~~~~~~
events.cpp:39:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |    st[i][j]=cmb(st[i][j-1], st[i+(1<<j-1)][j-1]);
      |                                      ~^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30