#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef long long int ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
#define prt(x) #x << ": " << x
#define sz(x) (int)(x).size()
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
#define pb push_back
#define vt vector
#define s second
#define f first
template <class A, class B> ostream &operator<<(ostream &out, const pair<A, B> &a){
return out << "(" << a.f << ", " << a.s << ")";
}
template <class A> ostream &operator<<(ostream &out, const vector<A> &v){
out << "[";
for (int i = 0; i < sz(v); ++i) {
if (i)
out << ", ";
out << v[i];
}
return out << "]";
}
template <int MOD> struct ModInt{
unsigned x;
ModInt() : x(0) { }
ModInt(signed sig) : x(sig) { }
ModInt(signed long long sig) : x(sig%MOD) { }
int get() const { return (int)x; }
ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
bool operator<(ModInt that) const { return x < that.x; }
friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};
typedef ModInt<1000000007> mint;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, inf = 0x3f3f3f3f, mxn = 2e5 + 5;
const int blck = 1877;
multiset<pair<int, pii>> temp;
vt<int> b_block[blck + 1], k_block_a[blck + 1], k_block_b[blck + 1];
vt<pii> v;
void add(int l, int r)
{
temp.insert({ r - l + 1, { l, r } });
}
void del(int idx)
{
int l = v[idx].f, r = v[idx].s;
temp.erase(temp.find({ r - l + 1, { l, r } }));
}
void calc(int idx)
{
for(auto i : temp){
b_block[idx].pb(i.f);
k_block_a[idx].pb(i.s.f);
k_block_b[idx].pb(i.s.s);
}
sort(all(k_block_a[idx]));
sort(all(k_block_b[idx]));
temp.clear();
}
int get(int l, int r, int k, int idx)
{
int s = 0, s1 = 0, s2 = 0;
for(int i = 1; i <= idx; ++i){
auto it = lb(all(b_block[i]), k);
if(it != b_block[i].end()){
s += sz(b_block[i]) - (it - b_block[i].begin());
}
it = ub(all(k_block_a[i]), r - k + 1);
if(it != k_block_a[i].end()){
s1 += sz(k_block_a[i]) - (it - k_block_a[i].begin());
}
it = ub(all(k_block_b[i]), k + l - 1);
if(it != k_block_b[i].begin()){
--it;
s2 += (it - k_block_b[i].begin()) + 1;
}
}
return s - s1 - s2;
}
int brute(int l, int r, int k)
{
int s = 0, s1 = 0, s2 = 0;
for(auto i : temp){
if(i.f >= k){
++s;
if(r - i.s.f + 1 < k){
++s1;
}
if(i.s.s - l + 1 < k){
++s2;
}
}
}
return s - s1 - s2;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q, t, lst = 0;
cin >> q >> t;
v.emplace_back();
for(int i = 1; i <= q; ++i){
int type;
cin >> type;
if(type == 1){
int a, b;
cin >> a >> b;
v.pb({ a, b });
add(a, b);
}
else if(type == 2){
int idx;
cin >> idx;
del(idx);
}
else{
int a, b, k;
cin >> a >> b >> k;
int l = (a ^ (t * lst)), r = (b ^ (t * lst));
if(l > r){
swap(l, r);
}
lst = get(l, r, k, (i - 1) / blck) + brute(l, r, k);
cout << lst << '\n';
}
if(i % blck == 0){
calc(i / blck);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
5052 ms |
472 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
3448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5058 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5072 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
5052 ms |
472 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
5052 ms |
472 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
