# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
931685 | 2024-02-22T09:16:33 Z | Yazan_Alattar | Advertisement 2 (JOI23_ho_t2) | C++14 | 254 ms | 72528 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define F first #define S second #define pb push_back #define endl "\n" #define all(x) x.begin(), x.end() const int M = 1000007; const ll inf = 1e9; const ll INF = 1e12; const ll mod = 1e9 + 7; const double eps = 1e-6; pair <ll,ll> a[M]; vector <ll> adj[M]; vector < pair <ll,ll> > order, values; ll n, ans; bool visit[M]; void solve(int _){ cin >> n; for(int i = 1; i <= n; ++i){ cin >> a[i].F >> a[i].S; order.pb({a[i].F, i}); values.pb({a[i].S, i}); } sort(all(order)); for(int i = 0; i < order.size(); ++i){ if(i > 0) adj[order[i].S].pb(order[i - 1].S); if(i + 1 < order.size()) adj[order[i].S].pb(order[i + 1].S); } sort(all(values), greater < pair <ll,ll> > ()); for(auto x : values){ int i = x.S; if(!visit[i]) ++ans; // cout << x.F << " " << i << " " << visit[i] << endl; for(auto j : adj[i]){ if(abs(a[i].F - a[j].F) <= a[i].S - a[j].S) visit[j] = 1; a[j].S = max(a[j].S, a[i].S - abs(a[i].F - a[i].S)); } } cout << ans << endl; return; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; ++i) solve(t); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 24924 KB | Output is correct |
2 | Correct | 55 ms | 37556 KB | Output is correct |
3 | Correct | 80 ms | 44320 KB | Output is correct |
4 | Correct | 223 ms | 69424 KB | Output is correct |
5 | Correct | 105 ms | 57804 KB | Output is correct |
6 | Correct | 254 ms | 72080 KB | Output is correct |
7 | Correct | 250 ms | 72220 KB | Output is correct |
8 | Correct | 245 ms | 72528 KB | Output is correct |
9 | Correct | 146 ms | 72396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 24920 KB | Output is correct |
2 | Correct | 5 ms | 24928 KB | Output is correct |
3 | Incorrect | 5 ms | 25056 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 24920 KB | Output is correct |
2 | Correct | 5 ms | 24928 KB | Output is correct |
3 | Incorrect | 5 ms | 25056 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 24924 KB | Output is correct |
2 | Correct | 55 ms | 37556 KB | Output is correct |
3 | Correct | 80 ms | 44320 KB | Output is correct |
4 | Correct | 223 ms | 69424 KB | Output is correct |
5 | Correct | 105 ms | 57804 KB | Output is correct |
6 | Correct | 254 ms | 72080 KB | Output is correct |
7 | Correct | 250 ms | 72220 KB | Output is correct |
8 | Correct | 245 ms | 72528 KB | Output is correct |
9 | Correct | 146 ms | 72396 KB | Output is correct |
10 | Correct | 5 ms | 24920 KB | Output is correct |
11 | Correct | 5 ms | 24928 KB | Output is correct |
12 | Incorrect | 5 ms | 25056 KB | Output isn't correct |
13 | Halted | 0 ms | 0 KB | - |