#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000000000;
const int MAX_M = 500000;
const int MAX_Q = 1000000;
const int MAX_R = MAX_M + MAX_Q;
int lastDSUNodeId = 0;
struct DSUNode {
int sef, val, rank, assignedRange;
vector<int> graph;
};
vector<DSUNode> dsu;
// find the boss of 'nod'
// O(logN)
int myfind(int nod) {
if(dsu[nod].sef == nod)
return nod;
return myfind(dsu[nod].sef);
}
// Unite node 'a' and node 'b'
// Union by rank
// O(logN)
int myunion(int a, int b) {
int sa = myfind(a), sb = myfind(b);
if(sa != sb) {
if(dsu[sa].rank < dsu[sb].rank) {
dsu[sa].sef = sb;
dsu[sb].graph.push_back(sa);
return sb;
} else {
dsu[sb].sef = sa;
dsu[sa].graph.push_back(sb);
if(dsu[sa].rank == dsu[sb].rank)
dsu[sa].rank++;
return sa;
}
}
return sa;
}
struct QueryRange {
int leftHead, rightHead;
} ranges[1+MAX_R];
// Put the ranges of the nodes assigned to the tree of 'nod' into vector 'target'
void unpackTree(int nod, vector<int> &target) {
dsu[nod].val = dsu[dsu[nod].sef].val;
if(nod == ranges[dsu[nod].assignedRange].leftHead ||
nod == ranges[dsu[nod].assignedRange].rightHead)
target.push_back(dsu[nod].assignedRange);
for(auto it: dsu[nod].graph)
unpackTree(it, target);
dsu[nod].graph.clear();
}
int assignDSUNode(int rangeId) {
dsu.push_back({0, 0, 0, rangeId});
lastDSUNodeId++;
return lastDSUNodeId - 1;
}
struct SegTree {
SegTree* left;
SegTree* right;
SegTree() {
left = right = NULL;
}
set<pair<int, int> > leftHalf;
set<pair<int, int> > rightHalf;
};
SegTree* segtree = NULL;
// Insert a range in the segment tree
void insertRange(SegTree* &T, int id, int x, int y, int l = 0, int r = MAX_N) {
int mid = (l + r) / 2;
if(T == NULL)
T = new SegTree();
if(x <= mid && mid + 1 <= y) { // Here is the current range's place
T->leftHalf.insert({x, ranges[id].leftHead});
T->rightHalf.insert({y, ranges[id].rightHead});
} else if(l < r) {
if(y <= mid)
insertRange(T->left, id, x, y, l, mid);
else
insertRange(T->right, id, x, y, mid + 1, r);
}
}
// Cut all values greater than or equal to val from given set
// return their union
void setCutRight(set<pair<int, int> > &myset, int val, vector<int> &target) {
while(!myset.empty() && myset.rbegin()->first >= val) {
target.push_back(myset.rbegin()->second);
myset.erase(*myset.rbegin());
}
}
// Cut all values less than or equal to val from given set
// return their union
void setCutLeft(set<pair<int, int> > &myset, int val, vector<int> &target) {
while(!myset.empty() && myset.begin()->first <= val) {
target.push_back(myset.rbegin()->second);
myset.erase(myset.begin());
}
}
// Cut ranges in segment tree by x or y. If one of them is -1, that update
// is disabled. One of the updates must be disabled
// Put all ranges in target
void pickupIntersecting(SegTree* &T, int x, int y, vector<int> &target,
int l = 0, int r = MAX_N) {
int mid = (l + r) / 2;
if(T == NULL)
return;
if(x != -1 && (x < l || r < x))
return;
if(y != -1 && (y < l || r < y))
return;
if(l < r) {
if(x != -1) {
if(x <= mid) { // Cut lefties
vector<int> lefties;
setCutLeft(T->leftHalf, x, lefties);
int newNode = -1;
for(int i = 0; i < lefties.size(); ++i)
if(i > 0)
newNode = myunion(lefties[i - 1], lefties[i]);
else
newNode = lefties[i];
if(newNode != -1) {
dsu[newNode].val = x;
T->leftHalf.insert(make_pair(dsu[newNode].val, newNode));
}
} else { // Get rid of lefties
vector<int> nodes;
setCutRight(T->rightHalf, x, nodes);
for(int i = 0; i < nodes.size(); ++i)
unpackTree(nodes[i], target);
}
} else if(y != -1) {
if(y > mid) {
vector<int> righties;
setCutRight(T->rightHalf, y, righties);
int newNode = -1;
for(int i = 0; i < righties.size(); ++i) {
if(i > 0)
newNode = myunion(righties[i - 1], righties[i]);
else
newNode = righties[i];
}
if(newNode != -1) {
dsu[newNode].val = y;
T->rightHalf.insert(make_pair(dsu[newNode].val, newNode));
}
} else {
vector<int> nodes;
setCutLeft(T->leftHalf, y, nodes);
for(int i = 0; i < nodes.size(); ++i) {
unpackTree(nodes[i], target);
}
}
}
pickupIntersecting(T->left, x, y, target, l, mid);
pickupIntersecting(T->right, x, y, target, mid + 1, r);
}
}
pair<int, int> queryRange(int rangeId) {
pair<int, int> rez;
int a = ranges[rangeId].leftHead;
int b = ranges[rangeId].rightHead;
a = myfind(a);
b = myfind(b);
rez = make_pair(dsu[a].val, dsu[b].val);
return rez;
}
void segTreeInsertRange(int x, int y, int id) {
ranges[id].leftHead = assignDSUNode(id);
ranges[id].rightHead = assignDSUNode(id);
dsu[ranges[id].leftHead] = {ranges[id].leftHead, x, 0, id};
dsu[ranges[id].rightHead] = {ranges[id].rightHead, y, 0, id};
insertRange(segtree, id, x, y);
}
// Cut the ranges with lUpd or rUpd
// If an update is -1, that means that there will be no update
void updateRange(int lUpd, int rUpd) {
vector<int> updatedRanges;
pickupIntersecting(segtree, lUpd, rUpd, updatedRanges);
for(auto it: updatedRanges) {
pair<int, int> oldRange = queryRange(it);
int x, y;
x = oldRange.first;
y = oldRange.second;
if(lUpd != -1)
x = lUpd;
if(rUpd != -1)
y = rUpd;
segTreeInsertRange(x, y, it);
}
}
int lastRangeId = 0;
void addRange(int x, int y) {
++lastRangeId;
segTreeInsertRange(x, y, lastRangeId);
}
int main() {
int N, M, Q;
scanf("%d%d%d", &N, &M, &Q);
for(int i = 0; i < M; ++i) {
int X, Y;
scanf("%d%d", &X, &Y);
addRange(X, N - Y);
}
for(int i = 0; i < Q; ++i) {
int T;
scanf("%d", &T);
if(T == 1) {
int P;
scanf("%d", &P);
pair<int, int> rez = queryRange(P);
printf("%d %d\n", rez.first,N - rez.second);
} else if(T == 2) {
int L;
scanf("%d", &L);
updateRange(N - L, -1);
} else if(T == 3) {
int L;
scanf("%d", &L);
updateRange(-1, L);
} else {
int A, B;
scanf("%d%d", &A, &B);
addRange(A, N - B);
}
}
return 0;
}
Compilation message
sweeping.cpp: In function 'void pickupIntersecting(SegTree*&, int, int, std::vector<int>&, int, int)':
sweeping.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < lefties.size(); ++i)
~~^~~~~~~~~~~~~~~~
sweeping.cpp:153:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < nodes.size(); ++i)
~~^~~~~~~~~~~~~~
sweeping.cpp:162:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < righties.size(); ++i) {
~~^~~~~~~~~~~~~~~~~
sweeping.cpp:177:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < nodes.size(); ++i) {
~~^~~~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:238:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &M, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:242:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &X, &Y);
~~~~~^~~~~~~~~~~~~~~~
sweeping.cpp:248:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &T);
~~~~~^~~~~~~~~~
sweeping.cpp:252:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &P);
~~~~~^~~~~~~~~~
sweeping.cpp:257:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &L);
~~~~~^~~~~~~~~~
sweeping.cpp:261:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &L);
~~~~~^~~~~~~~~~
sweeping.cpp:265:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A, &B);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4277 ms |
573768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3624 ms |
390924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3624 ms |
390924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
