이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5;
pii segments[nmax];
struct Oper {
int type;
int a, b;
int k;
};
namespace Precalc {
multiset<pii> actives;
void rebatch(vector<Oper> opqueue) {
for(auto [t, a, b, k] : opqueue) {
if(t == 1)
actives.insert(pii{a, b});
else if(t == 2)
actives.erase(actives.find(segments[a]));
}
return;
}
struct Item {
int link, sum, own;
};
#warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia
#warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
set<pii> fwrpoz;
set<pii> bckwpoz;
int freq[nmax];
Item fwr[nmax], bckw[nmax];
pii atrf[nmax], atrb[nmax];
map<int, int> norm_Ks;
vector<int> currKs;
int n;
void contextualize(vector<int> Ks) {
norm_Ks.clear();
for(auto x : Ks) norm_Ks[x];
int ptrnrm = 0;
for(auto &[a, b] : norm_Ks) b = ptrnrm++;
fwrpoz.clear(), bckwpoz.clear();
for(auto x : Ks) freq[norm_Ks[x]] = 0;
{ // forward links
map<pii, int> nrm;
for(auto [a, b] : actives) {
int k = b - a + 1;
if(k < Ks[0]) continue;
nrm[pii{a, b}];
}
vector<int> counter_app(sz(Ks));
n = 0;
for(auto &[a, b] : nrm) b = ++n, atrf[b] = a, fwr[b].sum = fwr[b].own = 0;
for(auto [a, b] : actives)
fwr[nrm[pii{a, b}]].own++;
map<int, int> for_links;
for(int i = n, atrcoef = sz(Ks) - 1; i > 0; atrcoef = (atrcoef == 0? sz(Ks) - 1 : atrcoef - 1), i--) {
auto [a, b] = atrf[i];
int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1)));
counter_app[poz] += fwr[i].own;
fwr[i].link = atrcoef;
fwr[i].sum = counter_app[atrcoef];
fwrpoz.emplace(pii{a, i});
//cerr << a << ' ' << b << '\t' << fwr[i].link << ' ' << ;
}
}
// ----
{ // backward links
auto cmp = [](const pii& a, const pii& b) -> bool { return a.second < b.second || (a.second == b.second && a.first < b.first); };
map<pii, int, decltype(cmp)> nrm(cmp);
for(auto [a, b] : actives) {
int k = b - a + 1;
if(k < Ks[0]) continue;
nrm[pii{a, b}];
}
vector<int> counter_app(sz(Ks));
n = 0;
for(auto &[a, b] : nrm) b = ++n, atrb[b] = a, bckw[b].sum = bckw[b].own = 0;
for(auto [a, b] : actives)
bckw[nrm[pii{a, b}]].own++;
map<int, int> for_links;
for(int i = 1, atrcoef = sz(Ks) - 1; i <= n; atrcoef = (atrcoef == 0? sz(Ks) - 1 : atrcoef - 1), i++) {
auto [a, b] = atrb[i];
int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1)));
counter_app[poz] += bckw[i].own;
bckw[i].link = atrcoef;
bckw[i].sum = counter_app[atrcoef];
bckwpoz.emplace(pii{b, i});
}
}
for(auto [a, b] : actives) {
int k = b - a + 1;
if(k < Ks[0]) continue;
freq[distance(begin(Ks), prev(upper_bound(all(Ks), k)))]++;
}
for(int i = sz(Ks) - 2; i >= 0; i--)
freq[i] += freq[i + 1];
currKs = move(Ks);
}
int query_K(int k) {
return freq[norm_Ks[k]];
}
int query_L(int L, int k) {
k = norm_Ks[k];
auto it = bckwpoz.upper_bound(pii{L + 1, - 1});
if(it == bckwpoz.begin()) return 0;
int poz = prev(it) -> second;
int rez = 0;
while(k < sz(currKs) && poz > 0) {
if(bckw[poz].link == k) {
rez += bckw[poz].sum;
k++;
}
if(k < sz(currKs) && currKs[k] <= atrb[poz].second - atrb[poz].first + 1) rez += bckw[poz].own;
poz--;
}
return rez;
}
int query_R(int R, int k) {
k = norm_Ks[k];
auto it = fwrpoz.upper_bound(pii{R, - 1});
if(it == fwrpoz.end()) return 0;
int poz = it -> second;
int rez = 0;
while(k < sz(currKs) && poz <= n) {
if(fwr[poz].link == k) {
rez += fwr[poz].sum;
k++;
}
if(k < sz(currKs) && currKs[k] <= atrf[poz].second - atrf[poz].first + 1) rez += fwr[poz].own;
poz++;
}
return rez;
}
}
//#error in loc sa ai pozitii care corespund unor segmente bune, doar pune suma partiala a alora congruenti cu (-pozitia) mod sz(Ks)
int segmpoz = 1;
int unitValue(int l, int r, int a, int b, int k) {
return min(r, b) - max(l, a) + 1 >= k;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, t_offline;
cin >> n >> t_offline;
const int idealBuck = min(5., ceil(sqrt(n * log2(n))));
const ll worstInner = (ll)ceil(idealBuck / 2) * ceil(idealBuck / 2) + 5;
vector<Oper> operation_queue;
int lastans = 0;
auto flush_queue = [&]() {
vector<int> Ks;
for(auto [t, a, b, k] : operation_queue)
if(t == 3) Ks.emplace_back(k);
if(sz(Ks) == 0) return;
sort(all(Ks));
Ks.erase(unique(all(Ks)), Ks.end());
Precalc::contextualize(Ks);
for(int i = 0; i < sz(operation_queue); i++) {
auto &[ti, ai, bi, ki] = operation_queue[i];
if(ti == 1 || ti == 3) {
ai = ai ^ (t_offline * lastans);
bi = bi ^ (t_offline * lastans);
if(ai > bi) swap(ai, bi);
}
if(ti == 1)
segments[segmpoz++] = pii{ai, bi};
if(ti == 3) {
if(bi - ai + 1 < ki) {
lastans = 0;
}
else {
int rez = Precalc::query_K(ki) - Precalc::query_R(bi - ki + 1 + 1, ki) - Precalc::query_L(ai + ki - 1 - 1, ki);
for(int j = i - 1; j >= 0; j--) {
auto &[tj, aj, bj, kj] = operation_queue[j];
if(tj == 3) continue;
else if(tj == 2)
rez -= unitValue(ai, bi, segments[aj].first, segments[aj].second, ki);
else
rez += unitValue(ai, bi, aj, bj, ki);
}
lastans = rez;
}
cout << lastans << '\n';
}
}
Precalc::rebatch(operation_queue);
operation_queue.clear();
};
int cnt[2] = {1, 0};
for(int t, a, b, k, tc = 0; tc < n; tc++) {
cin >> t;
if(t == 1) {
cin >> a >> b;
operation_queue.emplace_back(Oper{t, a, b, -1});
cnt[0]++;
}
if(t == 2) {
cin >> a;
operation_queue.emplace_back(Oper{t, a, -1, -1});
cnt[0]++;
}
if(t == 3) {
cin >> a >> b >> k;
operation_queue.emplace_back(Oper{t, a, b, k});
cnt[1]++;
}
if(tc == n - 1 || sz(operation_queue) >= idealBuck) {
flush_queue();
cnt[0] = 1;
cnt[1] = 0;
}
}
return 0;
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp:42:4: warning: #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia [-Wcpp]
42 | #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia
| ^~~~~~~
segments.cpp:43:4: warning: #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) [-Wcpp]
43 | #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
| ^~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:197:12: warning: unused variable 'worstInner' [-Wunused-variable]
197 | const ll worstInner = (ll)ceil(idealBuck / 2) * ceil(idealBuck / 2) + 5;
| ^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |