#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = b; i >= a; --i)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define REPD(i, a, b) for(int i = b; i > a; -- i)
#define ALL(v) v.begin(),v.end()
#define next __next
#define left __left
#define right __right
#define prev __prev
const int MOD[6] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277, 998244353};
const int BASE[6] = {23309, 300, 330, 280, 2309, 256};
const int base = BASE[0];
const int mod = MOD[0];
void add(int &u, int v){
u += v;
if(u >= mod) u -= mod;
}
void sub(int &u, int v){
u -= v;
if(u < 0) u += mod;
}
void minimize(int &u, int v){
if(u > v) u = v;
}
void maximize(int &u, int v){
if(u < v) u = v;
}
void minimizell(long long &u, long long v){
if(u > v) u = v;
}
void maximizell(long long &u, long long v){
if(u < v) u = v;
}
const int maxN = 80000 + 2;
const int maxM = 1e5 + 2;
const int maxK = 1e2 + 2;
const int INF = 1e9 + 8;
const long long INFLL = 1e18;
const int LOG = 16;
vector<int> adj[maxN];
int N, M;
struct Event{
int x, yA, yB, type, id;
}seg[2 * maxN];
bool cmp(const Event &A, const Event &B){
if(A.x != B.x) return A.x < B.x;
if(A.type == 3 && B.type == 1) return false;
if(A.type == 3 && B.type == 2) return true;
return false;
}
int xA[maxN], xB[maxN], yA[maxN], yB[maxN];
int X[maxN], Y[maxN], K[maxN];
int d[3 * maxN];// compress array
int par[maxN];
int curNode = 0;
stack<int> st[12 * maxN];
set<int> col[maxN];
int it[12 * maxN];
int lazy[12 * maxN];
void build(int id, int l, int r){
if(l == r){
lazy[id] = -1;
return ;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
lazy[id] = -1;
}
void push(int id){
lazy[id << 1] = lazy[id << 1 | 1] = it[id << 1] = it[id << 1 | 1] = lazy[id];
lazy[id] = -1;
}
void addRec(int id, int l, int r, int u, int v, int recId){
if(l > v || r < u)return ;
if(l >= u && r <= v){
st[id].push(recId);
it[id] = lazy[id] = recId;
return ;
}
int mid = l + r >> 1;
if(lazy[id] != -1)push(id);
addRec(id << 1, l, mid, u, v, recId);
addRec(id << 1 | 1, mid + 1, r, u, v, recId);
}
void revRec(int id, int l, int r, int u, int v){
if(l > v || r < u) return ;
if(l >= u && r <= v){
st[id].pop();
return ;
}
int mid = l + r >> 1;
revRec(id << 1, l, mid, u, v);
revRec(id << 1 | 1, mid + 1, r, u, v);
}
int get(int id, int l, int r, int u, int v){
if(l > v || r < u) return 0;
if(l >= u && r <= v){
return it[id];
}
int mid = l + r >> 1;
if(lazy[id] != -1)push(id);
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
void dfs(int u){
for(int v : adj[u]){
dfs(v);
for(set<int> :: iterator it = col[v].begin(); it != col[v].end(); ++it)col[u].insert(*it);
}
}
int degIn[maxN];
int main(){
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
//freopen(".INP", "w", stdout);
//freopen(".ANS", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> M;
int cnt = 0;
FOR(i, 1, N){
cin >> xA[i] >> yA[i] >> xB[i] >> yB[i];
d[++cnt] = yA[i];
d[++cnt] = yB[i];
}
FOR(i, 1, M){
cin >> X[i] >> Y[i] >> K[i];
d[++cnt] = Y[i];
}
sort(d + 1, d + 1 + cnt);
int cntEvent = 0;
FOR(i, 1, N){
yA[i] = lower_bound(d + 1, d + 1 + cnt, yA[i]) - d;
yB[i] = lower_bound(d + 1, d + 1 + cnt, yB[i]) - d;
seg[++cntEvent] = {xA[i], yA[i], yB[i], 1, i};
seg[++cntEvent] = {xB[i], yA[i], yB[i], 2, i};
}
FOR(i, 1, M){
Y[i] = lower_bound(d + 1, d + 1 + cnt, Y[i]) - d;
seg[++cntEvent] = {X[i], Y[i], Y[i], 3, K[i]};
}
sort(seg + 1, seg + 1 + cntEvent, cmp);
FOR(i, 1, cntEvent){
Event &tmp = seg[i];
if(tmp.type == 1){
int p = get(1, 1, cnt, tmp.yA, tmp.yB);
if(p){
adj[p].push_back(tmp.id);
par[tmp.id] = p;
degIn[tmp.id]++;
}
addRec(1, 1, cnt, tmp.yA, tmp.yB, tmp.id);
// addSegment(1, 1, cnt, tmp.yA, tmp.yB, tmp.id);
}
else if(tmp.type == 2){
revRec(1, 1, cnt, tmp.yA, tmp.yB);
int pre = get(1, 1, cnt, yA[par[tmp.id]], yB[par[tmp.id]]);
addRec(1, 1, cnt, tmp.yA, tmp.yB, pre);
// cout << inRec(1, 1, cnt, tmp.yA, tmp.yB) << "\n";
// FOR(i, tmp.yA, tmp.yB)cout << inRec(1, 1, cnt, i, i) << ' ';cout << "\n";
}
else{
int node = get(1, 1, cnt, tmp.yA, tmp.yA);
if(node){
col[node].insert(tmp.id);
}
}
}
for(int i = 1; i <= N; ++i){
if(degIn[i] == 0)dfs(i);
}
FOR(i, 1, N)cout << col[i].size() << '\n';
return 0;
}
Compilation message
plahte.cpp: In function 'void build(int, int, int)':
plahte.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid = l + r >> 1;
| ~~^~~
plahte.cpp: In function 'void addRec(int, int, int, int, int, int)':
plahte.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = l + r >> 1;
| ~~^~~
plahte.cpp: In function 'void revRec(int, int, int, int, int)':
plahte.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid = l + r >> 1;
| ~~^~~
plahte.cpp: In function 'int get(int, int, int, int, int)':
plahte.cpp:107:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
107 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
180 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
206 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
179 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
