// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
struct SET{
map<int, int> mp;
void add(int f, int s, int x){
auto L = mp.upper_bound(f);
int col = -1;
if(L != mp.begin())
col = prev(L)->S;
auto R = L;
while(R != mp.end() && (R->F) <= s)
col = R->S, R++;
mp[f] = x;
mp[s] = col;
}
int ask(int pos){
auto it = mp.upper_bound(pos);
if(it == mp.begin())
return -1;
return prev(it)->S;
}
};
vector<int> arr;
struct segment{
SET s[4 * 2 * maxn];
void add(int fx, int sx, int fy, int sy, int x, int l = 0, int r = sz(arr) - 1, int id = 1){
if(fx <= arr[l] && arr[r] <= sx){
s[id].add(fy, sy, x);
return;
}
int mid = (l+r) >> 1;
if(sx > arr[l] && arr[mid] > fx)
add(fx, sx, fy, sy, x, l, mid, 2 * id);
if(sx > arr[mid] && arr[r] > fx)
add(fx, sx, fy, sy, x, mid, r, 2 * id + 1);
}
int ask(int posx, int posy, int l = 0, int r = sz(arr) - 1, int id = 1){
if(r-l == 1)
return s[id].ask(posy);
int mid = (l+r) >> 1;
if(posx < arr[mid])
return max( s[id].ask(posy), ask(posx, posy, l, mid, 2*id) );
else
return max( s[id].ask(posy), ask(posx, posy, mid, r, 2*id+1) );
}
};
int N;
pii trans(pii p){ // x1 x2
return {p.S, N - p.F};
}
pii trans2(pii p){ // x1 x2
return {p.F, N - p.S};
}
struct bigTraingle{
map<pii, pii> mp;
vector<pii> to;
segment seg;
void restart(){
mp.clear();
to.clear();
ins({0, N}, {0, 0});
}
pii color(pii p){
int c = seg.ask(p.F, p.S);
return to[c];
}
void put(pii l, pii r, pii x){
assert(*lower_bound(arr.begin(), arr.end(), l.F) == l.F);
assert(*lower_bound(arr.begin(), arr.end(), r.F + 1) == r.F + 1);
seg.add(l.F, r.F + 1, l.S, r.S + 1, sz(to));
to.PB(x);
}
void ins(pii a, pii b){
mp[a] = b;
put(b, trans(a), a);
}
void add(int l, bool is){
int x = l, y = N - l;
if(is)
swap(x, y);
auto it = --mp.upper_bound({x, inf});
int L = it->F.F, R = it->F.S;
pii p = it->S;
mp.erase(it);
if(!is){
pii A = {L, x}, B = {x + 1, R};
ins(A, p);
if(B.F <= B.S)
ins(B, {B.F, p.S});
}
else{
pii A = {L, x - 1}, B = {x, R};
ins(B, p);
if(A.F <= A.S)
ins(A, {p.F, N - A.S});
}
}
pii calc(pii p){
pii s = color(p);
pii A = mp[s], B = trans(s), C = trans2(s);
assert(A.F <= p.F && A.S <= p.S && p.F <= B.F && p.S <= B.S);
return {max(C.F, p.F), max(C.S, p.S)};
}
};
bigTraingle tr[20];
vector<int> ids[20];
int who[maxn];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
int m, q;
cin >> N >> m >> q;
vector<pii> p;
for(int i = 0; i < 20; i++){
if(bit(m, i)){
for(int j = 0; j < (1<<i); j++){
int x, y;
cin >> x >> y;
who[sz(p)] = i;
ids[i].PB(sz(p));
p.PB({x, y});
}
}
}
stringstream CIN;
for(int i = 0; i < q; i++){
int task, a, b;
cin >> task >> a;
CIN << task << " " << a << " ";
if(task == 4){
cin >> b;
CIN << b << " ";
}
if(task == 2){
arr.PB(N - a);
arr.PB(a+2);
}
if(task == 3){
arr.PB(a + 1);
}
}
arr.PB(0);
arr.PB(N);
arr.PB(N+1);
sort(arr.begin(), arr.end());
arr.resize( unique(arr.begin(), arr.end()) - arr.begin() );
// should be next of arr
for(int i = 0; i < 20; i++){
tr[i].restart();
}
while(q--){
int task;
CIN >> task;
if(task == 1){
int id;
CIN >> id;
--id;
pii ans = tr[who[id]].calc(p[id]);
cout << ans.F << " " << ans.S << "\n";
}
if(task == 2){
int l;
CIN >> l;
for(int i = 0; i < 20; i++)
if(!ids[i].empty())
tr[i].add(l, 1);
}
if(task == 3){
int l;
CIN >> l;
for(int i = 0; i < 20; i++)
if(!ids[i].empty())
tr[i].add(l, 0);
}
if(task == 4){
int x, y;
CIN >> x >> y;
vector<int> vv;
vv.PB(sz(p));
p.PB({x, y});
int pt = 0;
while(!ids[pt].empty()){
for(int x : ids[pt])
vv.PB(x), p[x] = tr[pt].calc(p[x]);
ids[pt].clear();
tr[pt].restart();
pt++;
}
swap(ids[pt], vv);
for(int x : ids[pt]){
who[x] = pt;
}
}
}
return 0;
}
Compilation message
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<wchar_t>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIwEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<char>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIcEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa1): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x24f): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa9): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x114): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x294): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
