Submission #681221

#	Time	Username	Problem	Language	Result	Execution time	Memory
681221		DanTatar	Segments (IZhO18_segments)	C++17	7 / 100	998 ms	5668 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>

/*#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,id;
    int len(){
        return r - l + 1;
    }
};

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

node seg[N];
int cur = 1;
int n,t;
vector <int> cur_seg, del_seg;
vector <vector<int>> aB, bB;
int B,maxB;
int last;
vector <node> q;
bool del[N];

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

void update(){
    del_seg.clear();
    cur_seg.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 < maxB; ++i){
        aB[i].clear();
        bB[i].clear();
    }

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

    for(int i = 0; i < maxB; ++i){
        sort(all(aB[i]));
        sort(all(bB[i]));
    }
}

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

    return res;
}

int binsearch(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 = binsearch(k);
    int S1 = 0;
    for(int i = 0; i < S/B; ++i){
        int p = upper_bound(all(aB[i]), x.r-k+1)-aB[i].begin();
        p = sz(aB[i]) - p;
        S1 += p;
        p = lower_bound(all(bB[i]), k + x.l + 1) - bB[i].begin();
        S1 += p;
    }

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

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

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

    S -= S1;

    return last=S;
}

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

	return cnt+1;
}

void solve(){
    cin >> n >> t;
    B = sqrt(n * lg(n));
    maxB = n/B+2;
    aB.resize(maxB), bB.resize(maxB);
    for(int i = 1; i <= n; ++i){
        int type;
        cin >> type;
        if(i % B == 0){
            update();
        }

        //cout << "OK" << ent;

        if(type == 1){
            int l,r;
            cin >> l >> r;
            cur_seg.pb(cur);
            seg[cur].id = cur;
            seg[cur++] = decode(l, r);
        } else if(type == 2){
            int ind;
            cin >> ind;
            del_seg.pb(ind);
            del[ind] = 1;
        } else {
            int l,r,k;
            cin >> l >> r >> k;
            cout << get(decode(l, r), k) << ent;
        }
    }
}

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

Compilation message (stderr)

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

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