| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159472 |
2019-10-22T21:05:19 Z |
Atalasion |
Plahte (COCI17_plahte) |
C++14 |
|
639 ms |
110448 KB |
//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 160000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;
int n, m, col[N], par[N];
ll lazy[N << 4];
vi COL[N];
pair<pii, pii> rect[N];
pii poi[N];
vector<int> Px, Py;
vector<pair<pii, int>> vl[N << 2], vr[N << 2];
vector<pii> Ge[N << 2];
unordered_map<int, int> kojx, kojy;
void modify(int id, ll x){
lazy[id] += x;
return;
}
void shift(int id){
modify(id << 1, lazy[id]);
modify(id << 1 | 1, lazy[id]);
lazy[id] = 0;
return;
}
void add(int id, int lq, int rq, int x, int l, int r){
if (rq <= l || r <= lq) return;
if (lq <= l && r <= rq){
modify(id, x);
return;
}
int mid = (l + r) >> 1;
shift(id);
add(id << 1, lq, rq, x, l, mid);
add(id << 1 | 1, lq, rq, x, mid, r);
//seg[id] = seg[id << 1] + seg[id << 1 | 1];
return;
}
ll get(int id, int lq, int rq, int l, int r){
if (rq <= l || r <= lq) return 0;
if (lq <= l && r <= rq){
return lazy[id];
}
shift(id);
int mid = (l + r) >> 1;
return get(id << 1, lq, rq, l, mid) + get(id << 1 | 1, lq, rq, mid, r);
}
vi G[N], sub_t[N];
int child[N], cnt[N], ans[N];
void DFS_c(int v = 0, int p = 0){
child[v] += COL[v].size();
for (auto u:G[v]){
if (u == p) continue;
DFS_c(u, v);
child[v] += child[u];
}
return;
}
void DFS(int v = 0, int p = 0, bool f = 1){
int Mx = -1, ind = N - 1;
for (auto u:G[v]){
if (u == p) continue;
if (Mx < child[u]) Mx = child[u], ind = u;
}
for (auto u:G[v]){
if (u == p || u == ind) continue;
DFS(u, v, 0);
}
if (ind != N - 1) DFS(ind, v, 1);
ans[v] = ans[ind];
sub_t[v].swap(sub_t[ind]);
for (auto u:G[v]){
if (u == p || u == ind) continue;
for (auto x:sub_t[u]){
cnt[col[x]] ++;
sub_t[v].pb(x);
if (cnt[col[x]] == 1) ans[v]++;
}
sub_t[u].shrink_to_fit();
}
for (auto u:COL[v]){
cnt[col[u]]++;
if (cnt[col[u]] == 1) ans[v]++;
sub_t[v].pb(u);
}
// cout << v << '\n';
// for (int i = 1; i <= 3; i++) cout << cnt[i] << ' ';
// cout << '\n';
if (f == 0){
for (auto u:sub_t[v]){
cnt[col[u]] --;
}
}
return;
}
void solve(){
DFS_c(0);
DFS();
return;
}
vector<int> CC;
map<int, int> kojC;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
rect[i] = {{x1, y1}, {x2, y2}};
Px.pb(x1), Px.pb(x2), Py.pb(y1), Py.pb(y2);
}
for (int i = 1; i <= m; i++){
cin >> poi[i].F >> poi[i].S >> col[i];
CC.pb(col[i]);
Px.pb(poi[i].F), Py.pb(poi[i].S);
}
sort(all(CC));
CC.resize(unique(all(CC)) - CC.begin());
for (int i = 0; i < CC.size(); i++){
kojC[CC[i]] = i + 1;
}
for (int i = 1; i <= m; i++){
col[i] = kojC[col[i]];
}
sort(all(Px));
sort(all(Py));
Px.resize(unique(all(Px)) - Px.begin());
Py.resize(unique(all(Py)) - Py.begin());
for (int i = 0; i < Px.size(); i++) kojx[Px[i]] = i + 1;
for (int i = 0; i < Py.size(); i++) kojy[Py[i]] = i + 1;
for (int i = 1; i <= n; i++){
vl[kojx[rect[i].F.F]].pb({{kojy[rect[i].F.S], kojy[rect[i].S.S]}, i});
vr[kojx[rect[i].S.F]].pb({{kojy[rect[i].F.S], kojy[rect[i].S.S]}, i});
}
for (int i = 1; i <= m; i++){
Ge[kojx[poi[i].F]].pb({kojy[poi[i].S], i});
}
//return 0;
for (int i = 1; i < (N << 2); i++){
for (auto u:vl[i]){
//cout << u.S << '\n';
//cout << u.F.F << ' ' << u.F.S << '\n';
par[u.S] = get(1, u.F.F, u.F.F + 1, 1, (N << 2));
add(1, u.F.F, u.F.S + 1, u.S - par[u.S], 1, (N << 2));
}
for (auto u:Ge[i]){
ll dad = get(1, u.F, u.F + 1, 1, (N << 2));
// if (u.S == 1) dad = 1;
COL[dad].pb(u.S);
//cout << u.S << ' ' << dad << '\n';
}
for (auto u:vr[i]){
add(1, u.F.F, u.F.S + 1, par[u.S] - u.S, 1, (N << 2));
}
vl[i].shrink_to_fit();
vr[i].shrink_to_fit();
Ge[i].shrink_to_fit();
}
//for (int i = 1; i <= n; i++) cout << par[i] << ' ';
for (int i = 1; i <= n; i++){
G[par[i]].pb(i);
G[i].pb(par[i]);
}
//cout << '\n';
//return 0;
solve();
for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
return 0;
}
/*
5 3
1 1 11 10
2 7 7 9
6 2 9 6
7 4 8 5
3 2 5 4
4 6 1
6 8 3
8 5 2
*/
Compilation message
plahte.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
#pragma GCC optimise ("ofast")
plahte.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
#pragma GCC optimise("unroll-loops")
plahte.cpp: In function 'int main()':
plahte.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < CC.size(); i++){
~~^~~~~~~~~~~
plahte.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Px.size(); i++) kojx[Px[i]] = i + 1;
~~^~~~~~~~~~~
plahte.cpp:154:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Py.size(); i++) kojy[Py[i]] = i + 1;
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
71504 KB |
Output is correct |
| 2 |
Correct |
212 ms |
71108 KB |
Output is correct |
| 3 |
Correct |
60 ms |
56880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
75332 KB |
Output is correct |
| 2 |
Correct |
235 ms |
74052 KB |
Output is correct |
| 3 |
Correct |
60 ms |
56824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
388 ms |
89620 KB |
Output is correct |
| 2 |
Correct |
369 ms |
84728 KB |
Output is correct |
| 3 |
Correct |
59 ms |
56824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
611 ms |
110448 KB |
Output is correct |
| 2 |
Correct |
585 ms |
99480 KB |
Output is correct |
| 3 |
Correct |
60 ms |
56824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
639 ms |
108772 KB |
Output is correct |
| 2 |
Correct |
568 ms |
97256 KB |
Output is correct |
| 3 |
Correct |
62 ms |
56824 KB |
Output is correct |
