Submission #335279

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
335279	2020-12-11 19:30:41	Plurm	Railway Trip (JOI17_railway_trip)	C++11	20 / 100	2086 ms	12524 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;
vector<int> g[100005]; // cartesian-tree-like graph
int d[100005];
vector<int> bckt[100005];
int l[100005];
int n,k,q;
void compute(int a){
  d[a] = 0;
  for(int i = 1; i <= k; i++){
    for(int x : bckt[i]){
      for(int y : g[x]) d[x] = min(d[x], d[y]+1);
    }
    reverse(bckt[i].begin(), bckt[i].end());
    for(int x : bckt[i]){
      for(int y : g[x]) d[x] = min(d[x], d[y]+1);
    }
    reverse(bckt[i].begin(), bckt[i].end());
  }
}
int main(){
  scanf("%d%d%d",&n,&k,&q);
  stack<int> stk;
  for(int i = 1; i <= n; i++){
    scanf("%d", l+i);
    bckt[l[i]].push_back(i);
    while(!stk.empty() && l[stk.top()] <= l[i]){
      g[i].push_back(stk.top());
      stk.pop();
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d%d",&n,&k,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d", l+i);
      |   ~~~~~^~~~~~~~~~~
railway_trip.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

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