| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159653 |
2019-10-23T18:04:49 Z |
ruler |
Plahte (COCI17_plahte) |
C++14 |
|
525 ms |
141356 KB |
// IOI 2021
#include <bits/stdc++.h>
using namespace std;
#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9, MOD = INF + 7;
/////////////////////////////////////////////////////////////////////
const int N = 1e6 + 5;
struct Point { int x = 0, y = 0, c = 0; };
struct Rect { Point l, r; };
Rect sheets[N];
Point shots[N];
vector< pair<pii, int> > swpL[N], swpR[N];
vector<pii> swpD[N];
int seg[4 * N], par[N], st[N], fn[N], ver[N], cnt[N], ans[N], sz[N], ts, tot;
vector<int> cols[N], g[N];
int get(int p, int id = 1, int s = 0, int e = N) {
if (e - s < 2) return seg[id];
int md = (s + e) / 2;
if (p < md) return seg[id] + get(p, 2 * id, s, md);
else return seg[id] + get(p, 2 * id + 1, md, e);
}
void update(int l, int r, int val, int id = 1, int s = 0, int e = N) {
if (l <= s && e <= r) {
seg[id] += val;
return;
}
if (l >= e || s >= r) return;
int md = (s + e) / 2;
update(l, r, val, 2 * id, s, md);
update(l, r, val, 2 * id + 1, md, e);
}
void add(int c) { if (cnt[c]++ == 0) tot++; }
void del(int c) { if (--cnt[c] == 0) tot--; }
int pre(int v = 0) {
st[v] = ts++, ver[st[v]] = v;
sz[v] += sz(cols[v]);
for (int u : g[v]) sz[v] += pre(u);
fn[v] = ts;
return sz[v];
}
void dfs(int v = 0, bool keep = 0) {
int big = -1;
for (int u : g[v]) if (big == -1 || sz[big] < sz[u]) big = u;
for (int u : g[v]) if (u != big) dfs(u, 0);
if (big != -1) dfs(big, 1);
for (int u : g[v]) if (u != big) {
for (int t = st[u]; t < fn[u]; t++) {
int w = ver[t];
for (int c : cols[w]) add(c);
}
}
for (int c : cols[v]) add(c);
ans[v] = tot;
if (!keep) {
for (int t = st[v]; t < fn[v]; t++) {
int w = ver[t];
for (int c : cols[w]) del(c);
}
}
}
int main() {
sync;
int n, m; cin >> n >> m;
vector<int> compX, compY, compC;
for (int i = 1; i <= n; i++) {
Rect &rec = sheets[i];
cin >> rec.l.x >> rec.l.y >> rec.r.x >> rec.r.y;
compX.push_back(rec.l.x);
compX.push_back(rec.r.x);
compY.push_back(rec.l.y);
compY.push_back(rec.r.y);
}
for (int i = 1; i <= m; i++) {
Point &poi = shots[i];
cin >> poi.x >> poi.y >> poi.c;
compX.push_back(poi.x);
compY.push_back(poi.y);
compC.push_back(poi.c);
}
sort(all(compX)); compX.resize(unique(all(compX)) - compX.begin());
sort(all(compY)); compY.resize(unique(all(compY)) - compY.begin());
sort(all(compC)); compC.resize(unique(all(compC)) - compC.begin());
for (int i = 1; i <= n; i++) {
Rect &rec = sheets[i];
rec.l.x = lower_bound(all(compX), rec.l.x) - compX.begin() + 1;
rec.l.y = lower_bound(all(compY), rec.l.y) - compY.begin() + 1;
rec.r.x = lower_bound(all(compX), rec.r.x) - compX.begin() + 1;
rec.r.y = lower_bound(all(compY), rec.r.y) - compY.begin() + 1;
swpL[rec.l.x].push_back(make_pair(make_pair(rec.l.y, rec.r.y), i));
swpR[rec.r.x].push_back(make_pair(make_pair(rec.l.y, rec.r.y), i));
}
for (int i = 1; i <= m; i++) {
Point &poi = shots[i];
poi.x = lower_bound(all(compX), poi.x) - compX.begin() + 1;
poi.y = lower_bound(all(compY), poi.y) - compY.begin() + 1;
swpD[poi.x].push_back(make_pair(poi.y, i));
}
for (int i = 1; i < N; i++) {
for (auto d : swpL[i]) {
par[d.second] = get(d.first.first);
update(d.first.first, d.first.second + 1, d.second - par[d.second]);
}
for (auto d : swpD[i]) {
int p = get(d.first);
cols[p].push_back(shots[d.second].c);
}
for (auto d : swpR[i]) {
update(d.first.first, d.first.second + 1, - d.second + par[d.second]);
}
}
for (int i = 1; i <= n; i++) g[par[i]].push_back(i);
pre();
dfs();
for (int i = 1; i <= n; i++) cout << ans[i] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
124020 KB |
Output is correct |
| 2 |
Correct |
225 ms |
123780 KB |
Output is correct |
| 3 |
Correct |
117 ms |
117880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
251 ms |
126444 KB |
Output is correct |
| 2 |
Correct |
248 ms |
125420 KB |
Output is correct |
| 3 |
Correct |
118 ms |
117880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
351 ms |
132532 KB |
Output is correct |
| 2 |
Correct |
350 ms |
129400 KB |
Output is correct |
| 3 |
Correct |
117 ms |
117880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
514 ms |
141048 KB |
Output is correct |
| 2 |
Correct |
525 ms |
141356 KB |
Output is correct |
| 3 |
Correct |
123 ms |
118036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
518 ms |
139728 KB |
Output is correct |
| 2 |
Correct |
513 ms |
140736 KB |
Output is correct |
| 3 |
Correct |
119 ms |
117880 KB |
Output is correct |
