Submission #1063355

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1063355	2024-08-17 17:09:57	Unforgettablepl	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2032 ms	95252 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 int long long
const int INF = 1e15;
void main2(int n,int k){
    int q;
    cin >> q;
    vector<int> l(n+1);
    vector<vector<int>> idxes(k+1);
    for(int i=1;i<=n;i++)cin>>l[i];
    vector<vector<int>> adj(n+1);
    stack<pair<int,int>> s;
    for(int i=1;i<=n;i++) {
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    while(!s.empty())s.pop();
    for(int i=n;i;i--){
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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