Submission #681264

#	Time	Username	Problem	Language	Result	Execution time	Memory
681264		DanTatar	Segments (IZhO18_segments)	C++17	100 / 100	2876 ms	15324 KiB

segments

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) v.size()
#define in insert
#define ld double
#define all(v) v.begin(),v.end()
#define ent endl
#define S second
#define F first
#define pii pair <int, int>
#define int long long

/*#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")*/

using namespace std;

const int INF = 1e18 + 123;
const int N = 2e5 + 123;
const int mod = 998244353;
const double PI = 3.1415926536;

const double eps = 1e-20;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

void speed(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct node{
    int l,r;
    int len(){
        return r-l+1;
    }
};

int n,t;
int B,m;
int last;
int del[N];
node seg[N];
vector <node> q;
vector <int> seg_cur, seg_del;
int cur = 1;
vector <vector<int>> L,R;

bool cmp(node a, node b){
    return a.len() > b.len();
}

int dist(int l,int r,int l1,int r1){
	if(l1 > r || r1 < l) return 0;
    return (int)min(r, r1) - (int)max(l, l1) + 1;
}

node decode(int a, int b){
    node tmp;
    tmp.l = (a^(t*last));
    tmp.r = (b^(t*last));
    if(tmp.l > tmp.r){
        swap(tmp.l, tmp.r);
    }

    return tmp;
}

int lg(int x){
    int res = 0;
    while(x){
        res ++;
        x/=2;
    }

    return res+1;
}

void add(node x){
    seg[cur] = x;
    seg_cur.pb(cur);
    cur ++;
}

void rem(int id){
    del[id] = 1;
    seg_del.pb(id);
}

void precalc(){
    seg_cur.clear();
    seg_del.clear();
    q.clear();
    for(int i = 1; i < cur; ++i){
        if(!del[i]){
            q.pb(seg[i]);
        }
    }

    sort(all(q), cmp);
    for(int i = 0; i < m; ++i){
        L[i].clear();
        R[i].clear();
    }

    for(int i = 0; i < sz(q); ++i){
        L[i/B].pb(q[i].l);
        R[i/B].pb(q[i].r);
    }

    for(int i = 0; i < m; ++i){
        sort(all(L[i]));
        sort(all(R[i]));
    }
}

int calc(int x){
    if(q.empty()) return 0;
	if(q.back().len() >= x) return sz(q);
	int l = -1, r = sz(q);
	while(l+1<r){
		int mid = (l+r)/2;
		if(q[mid].len() < x) r = mid;
		else l = mid;
	}

	return r;
}

int get(node x, int k){
    int S = calc(k);
    int S1 = 0;

    for(int i = 0; i < S/B; ++i){
        int p = upper_bound(all(L[i]), x.r-k+1) - L[i].begin();
        p = sz(L[i]) - p;
        S1 += p;
        p = lower_bound(all(R[i]), x.l+k-1) - R[i].begin();
        S1 += p;
    }

    int BB = S/B;
    for(int i = BB*B; i < min((BB+1ll)*B, (int)sz(q)); ++i){
        if(q[i].len() >= k && dist(x.l, x.r, q[i].l, q[i].r) < k){
            S1 ++;
        }
    }

    for(int i = 0; i < sz(seg_cur); ++i){
        int j = seg_cur[i];
        if(dist(x.l, x.r, seg[j].l, seg[j].r) >= k){
            S ++;
        }
    }

    for(int i = 0; i < sz(seg_del); ++i){
        int j = seg_del[i];
        if(dist(x.l, x.r, seg[j].l, seg[j].r) >= k){
            S --;
        }
    }

    S -= S1;
    return last=S;
}

void solve(){
    cin >> n >> t;
    B = sqrt(n*lg(n));
    m = n/B+2;

    L.resize(m);
    R.resize(m);

    for(int i = 1; i <= n; ++i){
        if(i%B==0){
            precalc();
        }

        int type;
        cin >> type;
        if(type == 1){
            int a,b;
            cin >> a >> b;
            add(decode(a,b));
        } else if(type == 2){
            int ind;
            cin >> ind;
            rem(ind);
        } else {
            int a,b,k;
            cin >> a >> b >> k;
            cout << get(decode(a,b), k) << ent;
        }
    }
}

signed main() {
	speed();
    int tt = 1;
    //cin >> tt;
    while(tt --){
        solve();
        cout << ent;
    }
}

Compilation message (stderr)

segments.cpp: In function 'void precalc()':
segments.cpp:113:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int i = 0; i < sz(q); ++i){
      |                      ^
segments.cpp: In function 'long long int get(node, long long int)':
segments.cpp:156:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0; i < sz(seg_cur); ++i){
      |                      ^
segments.cpp:163:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i = 0; i < sz(seg_del); ++i){
      |                      ^

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