oj.uz

답안 #893194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893194 2023-12-26T16:48:31 Z AgentPengin 버스 (JOI14_bus) C++14
35 / 100
 144 ms 37848 KB 
/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;
const int MAXM = 3e5 + 5;

struct Info {
	int u,t,id,type;
	bool operator < (const Info &other) const {
		if (t != other.t) return t < other.t;
		else return type < other.type;
	}
};

vector<Info> v;
int n,m,mx[MAXN],d[MAXN];
vector<pair<int,int>> dd[MAXN];

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (ifstream(NAME".inp")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
    	int u,V,s,t;
    	cin >> u >> V >> s >> t;
    	v.push_back({u,s,i,1});
    	v.push_back({V,t,i,0});
    }
    sort(bend(v));
    for (int i = 1;i <= n;i++) mx[i] = -1;
    for (auto x : v) {
    	if (x.type == 1) {
    		if (x.u == 1) d[x.id] = x.t;
    		else d[x.id] = mx[x.u];
    	} else {
    		if (d[x.id] != -1) {
    			dd[x.u].emplace_back(x.t,d[x.id]);
    			mx[x.u] = max(mx[x.u],d[x.id]);
    		}
    	}
    }
    for (int i = 1;i < sz(dd[n]);i++) dd[n][i].se = max(dd[n][i].se,dd[n][i - 1].se);
    int q; cin >> q;
    while(q--) {
    	int x; cin >> x;
    	int k = upper_bound(bend(dd[n]),make_pair(x,inf)) - dd[n].begin() - 1;
    	if (k == -1) cout << k << EL;
    	else cout << dd[n][k].se << EL;
    }
    
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// agent pengin wants to take apio (with anya-san)

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bus.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 2824 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 2 ms 2908 KB Output is correct
13 Correct 2 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 18 ms 4364 KB Output is correct
3 Correct 17 ms 4440 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 3 ms 2976 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 12 ms 3420 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 12 ms 3588 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 13 ms 3684 KB Output is correct
12 Correct 21 ms 4712 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 144 ms 37848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 140 ms 34732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -