| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 721288 |
2023-04-10T15:48:59 Z |
khshg |
Plahte (COCI17_plahte) |
C++14 |
|
717 ms |
49060 KB |
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second
template<class T> using V = vector<T>;
#define arr array
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)
template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }
const int maxn = 8e4 + 10;
int N, M, par[maxn], ans[maxn];
V<pair<pi, pi>> r;
V<pair<pi, int>> b;
map<int, int> cmpx, cmpy;
V<tuple<int, int, int, int, int>> events;
// x cordinate
// 0/2 - a sheet ; y cordinate ; length down ; id;
// 1 - a ball ; y cordinate ; color of the ball ; ignore this;
set<int> stl[maxn];
vi adj[maxn];
ll bit[3 * maxn];
void upd(int ind, int val) {
while(ind < 3 * maxn) {
bit[ind] += val;
ind += ind & -ind;
}
}
ll rino(int ind) {
ll res = 0;
while(ind > 0) {
res += bit[ind];
ind -= ind & -ind;
}
if(res < 0) {
cout << "NO\n";
exit(0);
}
return res;
}
void make(int y, int len, int id) {
ll t = rino(y);
upd(y + 1, t - id);
upd(y - len, id - t);
}
void dfs(int s) {
trav(u, adj[s]) {
dfs(u);
if(sz(stl[u]) > sz(stl[s])) swap(stl[u], stl[s]);
trav(v, stl[u]) stl[s].ins(v);
}
ans[s] = sz(stl[s]);
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
r.rsz(N);
F0R(i, N) {
cin >> r[i].ff.ff >> r[i].ff.ss >> r[i].ss.ff >> r[i].ss.ss;
cmpx[r[i].ff.ff];
cmpy[r[i].ff.ss];
cmpx[r[i].ss.ff];
cmpy[r[i].ss.ss];
}
b.rsz(M);
F0R(i, M) {
cin >> b[i].ff.ff >> b[i].ff.ss >> b[i].ss;
cmpx[b[i].ff.ff];
cmpy[b[i].ff.ss];
}
{
int tim3 = 1;
trav(u, cmpx) {
u.ss = tim3++;
}
tim3 = 1;
trav(u, cmpy) {
u.ss = tim3++;
}
F0R(i, N) {
r[i].ff.ff = cmpx[r[i].ff.ff];
r[i].ff.ss = cmpy[r[i].ff.ss];
r[i].ss.ff = cmpx[r[i].ss.ff];
r[i].ss.ss = cmpy[r[i].ss.ss];
events.eb(r[i].ff.ff, 0, r[i].ss.ss, r[i].ss.ss - r[i].ff.ss, i + 1);
events.eb(r[i].ss.ff, 2, r[i].ss.ss, r[i].ss.ss - r[i].ff.ss, i + 1);
}
F0R(i, M) {
b[i].ff.ff = cmpx[b[i].ff.ff];
b[i].ff.ss = cmpy[b[i].ff.ss];
events.eb(b[i].ff.ff, 1, b[i].ff.ss, b[i].ss, 0);
}
}
sor(events);
trav(u, events) {
int x, y; int ball; int c; int id;
tie(x, ball, y, c, id) = u;
if(ball == 1) {
stl[rino(y)].ins(c);
continue;
}
if(ball == 2) {
make(y, c, par[id]);
continue;
}
par[id] = rino(y);
make(y, c, id);
}
F0R(i, N) adj[par[i + 1]].pb(i + 1);
dfs(0);
F0R(i, N) cout << ans[i + 1] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
18432 KB |
Output is correct |
| 2 |
Correct |
136 ms |
20340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
21312 KB |
Output is correct |
| 2 |
Correct |
195 ms |
22188 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
332 ms |
32872 KB |
Output is correct |
| 2 |
Correct |
381 ms |
31584 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
687 ms |
49024 KB |
Output is correct |
| 2 |
Correct |
717 ms |
49060 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
651 ms |
47132 KB |
Output is correct |
| 2 |
Correct |
697 ms |
45448 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5972 KB |
Output is correct |
