Submission #116528

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
116528	2019-06-12 17:55:46	tmwilliamlin168	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	1595 ms	403016 KiB

railway_trip

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 d1 array<int, 2>
#define d2 array<d1, 2>
const int mxN=1e5, BS=400;
int n, k, q, l[17][mxN], ln1[mxN], ln2[mxN], ld[mxN], rn1[mxN], rn2[mxN], rd[mxN];
d1 p[mxN];
d2 nxts[mxN], nxtb[(mxN-1)/BS+1][mxN];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k >> q;
  for(int i=0; i<n; ++i) {
    cin >> l[0][i], --l[0][i];
    p[i]={l[0][i], i};
  }
  sort(p, p+n);
  for(int i=1; i<17; ++i)
    for(int j=0; j<=n-(1<<i); ++j)
      l[i][j]=max(l[i-1][j], l[i-1][j+(1<<i-1)]);
  for(int i=0; i<n; ++i) {
    ln1[i]=ln2[i]=i-1;
    while(~ln1[i]&&l[0][ln1[i]]<=l[0][i])
      ln1[i]=ln1[ln1[i]];
    while(~ln2[i]&&l[0][ln2[i]]<l[0][i])
      ln2[i]=ln2[ln2[i]];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55