oj.uz

답안 #893784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893784 2023-12-27T12:23:47 Z vjudge1 Segments (IZhO18_segments) C++17
0 / 100
 55 ms 65536 KB 
// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>

#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

using namespace std ;
using ll = long long ;
using ld = long double ;

/**
 * Description: Does not allocate storage for nodes with no data
 * Source: USACO Mowing the Field
 * Verification: ~
 */

const int SZ = 1<<17;
template<class T> struct node {
	T val = 0; node<T>* c[2];
	node() { c[0] = c[1] = NULL; }
	void upd(int ind, T v, int L = 0, int R = SZ-1) { // add v
		if (L == ind && R == ind) { val += v; return; }
		int M = (L+R)/2;
		if (ind <= M) {
			if (!c[0]) c[0] = new node();
			c[0]->upd(ind,v,L,M);
		} else {
			if (!c[1]) c[1] = new node();
			c[1]->upd(ind,v,M+1,R);
		}
		val = 0; for (int i = 0 ; i < 2 ; i++) if (c[i]) val += c[i]->val;
	}
	T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
		if (hi < L || R < lo) return 0;
		if (lo <= L && R <= hi) return val;
		int M = (L+R)/2; T res = 0;
		if (c[0]) res += c[0]->query(lo,hi,L,M);
		if (c[1]) res += c[1]->query(lo,hi,M+1,R);
		return res;
	}
	void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
		if (L != R) {
			int M = (L+R)/2;
			if (ind <= M) {
				if (!c[0]) c[0] = new node();
				c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
			} else {
				if (!c[1]) c[1] = new node();
				c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
			}
		}
		val = (c0?c0->val:0)+(c1?c1->val:0);
	}
};

node<int> _l, _r;

int n , t, idx = 0, last = 0, sz = 0 ;
vector<pair<int,int>> p ;

void insert(int l ,int r) {
    sz++ ;
    p[++idx] = {l, r} ;
    _l.upd(l, 1) ;
    _r.upd(r, 1) ;
//    cout << "add = " << l << ' ' << r << '\n' ;
}

void remove(int i) {
    sz-- ;
    auto [l, r] = p[i] ;
    _l.upd(l, -1) ;
    _r.upd(r, -1) ;
//    cout << "del = " << l << ' ' << r << '\n' ;
}

int query(int lo, int hi, int k) {
    int mn = lo + k - 2 ;
    int mx = hi - k + 2 ;
    int ret = sz ;
//    dbg(mn, mx, _l.get(mx, 20000000002), _r.get(0, mn + 2)) ;
    ret -= _l.query(mx , SZ - 1) ;
    ret -= _r.query(0, mn) ;
    last = ret ;
    return ret ;
}

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cin >> n >> t ;
    p.resize(n + 5) ;
    for (int i = 0 ; i < n ; i++) {
        int cmd ; cin >> cmd ;
        if (cmd == 1) {
            int a , b; cin >> a >> b ;
            int l = (a ^ (t * last)) ;
            int r = (b ^ (t * last)) ;
            if (l > r) swap(l, r) ;
            insert(l, r) ;
        } else if (cmd == 2) {
            int ind ; cin >> ind ;
            remove(ind) ;
        } else {
            int a , b, k ; cin >> a >> b >> k ;
            int l = (a ^ (t * last)) ;
            int r = (b ^ (t * last)) ;
            if (l > r) swap(l, r) ;
            cout << query(l, r, k) << "\n" ;
        }
    }
    return 0 ;
}

// 希望白银

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 53 ms 65536 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 55 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 53 ms 65536 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 53 ms 65536 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -