제출 #681368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681368		dohyunii	Segments (IZhO18_segments)	C++17	0 / 100	5072 ms	3448 KiB

segments

#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);
        }
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25