oj.uz

Submission #893197

# Submission time Handle Problem Language Result Execution time Memory
893197 2023-12-26T16:51:33 Z AgentPengin 버스 (JOI14_bus) C++14
100 / 100
 155 ms 39260 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 = 5e5 + 5;
const int MAXM = 5e5 + 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 14960 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 4 ms 15128 KB Output is correct
12 Correct 5 ms 14940 KB Output is correct
13 Correct 3 ms 14956 KB Output is correct
14 Correct 5 ms 14940 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 19 ms 15708 KB Output is correct
3 Correct 22 ms 15708 KB Output is correct
4 Correct 6 ms 15196 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 15 ms 15196 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 14 ms 15280 KB Output is correct
10 Correct 20 ms 15756 KB Output is correct
11 Correct 15 ms 15192 KB Output is correct
12 Correct 23 ms 16080 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 29320 KB Output is correct
2 Correct 136 ms 39180 KB Output is correct
3 Correct 134 ms 37560 KB Output is correct
4 Correct 135 ms 39260 KB Output is correct
5 Correct 134 ms 37880 KB Output is correct
6 Correct 136 ms 39200 KB Output is correct
7 Correct 135 ms 38588 KB Output is correct
8 Correct 140 ms 39108 KB Output is correct
9 Correct 138 ms 38828 KB Output is correct
10 Correct 135 ms 37620 KB Output is correct
11 Correct 139 ms 37984 KB Output is correct
12 Correct 131 ms 37296 KB Output is correct
13 Correct 130 ms 37300 KB Output is correct
14 Correct 136 ms 36296 KB Output is correct
15 Correct 137 ms 37176 KB Output is correct
16 Correct 49 ms 23484 KB Output is correct
17 Correct 49 ms 23752 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 30388 KB Output is correct
2 Correct 147 ms 38836 KB Output is correct
3 Correct 149 ms 37812 KB Output is correct
4 Correct 151 ms 37664 KB Output is correct
5 Correct 153 ms 38128 KB Output is correct
6 Correct 151 ms 39008 KB Output is correct
7 Correct 154 ms 38412 KB Output is correct
8 Correct 152 ms 38620 KB Output is correct
9 Correct 155 ms 37220 KB Output is correct
10 Correct 151 ms 37552 KB Output is correct
11 Correct 154 ms 38076 KB Output is correct
12 Correct 151 ms 37928 KB Output is correct
13 Correct 147 ms 36508 KB Output is correct
14 Correct 155 ms 37616 KB Output is correct
15 Correct 150 ms 38068 KB Output is correct
16 Correct 62 ms 24508 KB Output is correct