oj.uz

Submission #681221

# Submission time Handle Problem Language Result Execution time Memory
681221 2023-01-12T14:45:07 Z DanTatar Segments (IZhO18_segments) C++17
7 / 100
 998 ms 5668 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 7 ms 352 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 13 ms 596 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 11 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 9 ms 680 KB Output is correct
11 Correct 14 ms 612 KB Output is correct
12 Correct 14 ms 600 KB Output is correct
13 Correct 10 ms 596 KB Output is correct
14 Correct 11 ms 472 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 10 ms 468 KB Output is correct
18 Correct 13 ms 596 KB Output is correct
19 Correct 11 ms 468 KB Output is correct
20 Correct 11 ms 528 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 998 ms 5292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 2652 KB Output is correct
2 Correct 153 ms 2784 KB Output is correct
3 Correct 215 ms 2636 KB Output is correct
4 Correct 158 ms 2644 KB Output is correct
5 Incorrect 993 ms 5416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2892 KB Output is correct
2 Correct 150 ms 2884 KB Output is correct
3 Correct 151 ms 2888 KB Output is correct
4 Correct 155 ms 2824 KB Output is correct
5 Incorrect 988 ms 5668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 7 ms 352 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 13 ms 596 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 11 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 9 ms 680 KB Output is correct
11 Correct 14 ms 612 KB Output is correct
12 Correct 14 ms 600 KB Output is correct
13 Correct 10 ms 596 KB Output is correct
14 Correct 11 ms 472 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 10 ms 468 KB Output is correct
18 Correct 13 ms 596 KB Output is correct
19 Correct 11 ms 468 KB Output is correct
20 Correct 11 ms 528 KB Output is correct
21 Incorrect 998 ms 5292 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 7 ms 352 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 13 ms 596 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 11 ms 468 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 9 ms 680 KB Output is correct
11 Correct 14 ms 612 KB Output is correct
12 Correct 14 ms 600 KB Output is correct
13 Correct 10 ms 596 KB Output is correct
14 Correct 11 ms 472 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 10 ms 468 KB Output is correct
18 Correct 13 ms 596 KB Output is correct
19 Correct 11 ms 468 KB Output is correct
20 Correct 11 ms 528 KB Output is correct
21 Incorrect 998 ms 5292 KB Output isn't correct
22 Halted 0 ms 0 KB -