제출 #340152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340152		GioChkhaidze	Segments (IZhO18_segments)	C++17	23 / 100	5054 ms	3616 KiB

segments

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int N = 2e5 + 5;
const int Sq = 1100;

int A[N], B[N], C[N];
int n, u, t, bl, lastans;
int sq = 1200;

bool cmp(int x, int y) {
	return C[x] < C[y];
}

struct {
	vector < int > u, c, ol;
	vector < int > L[N / Sq], R[N / Sq]; 

	void insert(int id) {
		u.pb(id);
		if (u.size() == sq) {
			vector < int > c;
			c.reserve(u.size() + ol.size());
			sort(u.begin(), u.end(), cmp);
			merge(u.begin(), u.end(), ol.begin(), ol.end(), back_inserter(c));
			ol.swap(c); u.clear();
			
			for (int bl = 0; bl*sq < ol.size(); ++bl) {
				L[bl].clear(), R[bl].clear();
			}
			
			for (int i = 0; i < ol.size(); ++i) {
				bl = i / sq;
				L[bl].pb(A[ol[i]]);
				R[bl].pb(B[ol[i]]);
			}
			
			for (int bl = 0; bl*sq < ol.size(); ++bl) {
				sort(L[bl].begin(),L[bl].end());
				sort(R[bl].begin(),R[bl].end());
			}
		}
	}
	
	int solve(int l, int r, int k) {
		if (r - l + 1 < k) return 0;
		int ans = 0, s, f, S, F, i;
		for (i = 0; i < u.size(); ++i) 
			if (min(r, B[u[i]]) - max(l, A[u[i]]) + 1 >= k) 
				++ans;
		
		for (s = 0; s < ol.size(); s += sq) {
			f = min(s + sq - 1, (int)ol.size() - 1);

			if (C[ol[s]] >= k) {
				bl = f / sq;
				ans += f - s + 1;
				ans -= L[bl].end() - upper_bound(L[bl].begin(), L[bl].end(), r - k + 1); 
				ans -= lower_bound(R[bl].begin(), R[bl].end(), l + k - 1) - R[bl].begin();
			}
				else
			if (C[ol[f]] >= k) {
				for (i = s; i <= f; ++i) 
					if (min(r, B[ol[i]]) - max(l, A[ol[i]]) + 1 >= k)
						 ++ans;
			}
		}

		return ans;
	}
	
} rcur, cur;

int G(int &x, int &y) {
	x = (x ^ (t * lastans));
	y = (y ^ (t * lastans));
	if (x > y) swap(x, y);
	return y - x + 1;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> t;
	int ty, id, l, r, k;
	for (int i = 0; i < n; ++i) {
		cin >> ty;
		if (ty == 1) { 
			cin >> A[u] >> B[u]; 
			C[u] = G(A[u], B[u]);
			cur.insert(u), ++u;
		}
			else
		if (ty == 2) { 
			cin >> id; --id;
			rcur.insert(id);
		}
			else
		if (ty == 3) { 
			cin >> l >> r >> k; G(l, r);
			lastans = cur.solve(l, r, k) - rcur.solve(l, r, k);
			cout << lastans << "\n";
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In member function 'void<unnamed struct>::insert(int)':
segments.cpp:24:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |   if (u.size() == sq) {
      |       ~~~~~~~~~^~~~~
segments.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for (int bl = 0; bl*sq < ol.size(); ++bl) {
      |                     ~~~~~~^~~~~~~~~~~
segments.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for (int i = 0; i < ol.size(); ++i) {
      |                    ~~^~~~~~~~~~~
segments.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for (int bl = 0; bl*sq < ol.size(); ++bl) {
      |                     ~~~~~~^~~~~~~~~~~
segments.cpp: In member function 'int<unnamed struct>::solve(int, int, int)':
segments.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (i = 0; i < u.size(); ++i)
      |               ~~^~~~~~~~~~
segments.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (s = 0; s < ol.size(); s += sq) {
      |               ~~^~~~~~~~~~~
segments.cpp:50:22: warning: unused variable 'S' [-Wunused-variable]
   50 |   int ans = 0, s, f, S, F, i;
      |                      ^
segments.cpp:50:25: warning: unused variable 'F' [-Wunused-variable]
   50 |   int ans = 0, s, f, S, F, i;
      |                         ^
segments.cpp: At global scope:
segments.cpp:84:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main () {
      |       ^

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