Submission #40366

#	Time	Username	Problem	Language	Result	Execution time	Memory
40366		model_code	Segments (IZhO18_segments)	C++11	100 / 100	2844 ms	13376 KiB

segments

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()
#define sz(a) (int)a.size()

const int inf = (1ll << 30) - 1;
const int maxn = (int) 1e5 + 10;

inline int min(int a, int b){
	if(a<b) return a;
	return b;
}
inline int max(int a, int b){
	if(a>b) return a;
	return b;
}

using namespace std;

int A[544][544];
int B[544][544];
int L_pos[200200];
int R_pos[200200];
int pos[200200];
const int KK = 430;
int K = 4;
int G[744][944];
int L[744][944];
int R[744][944];
int szG[744];
int szL[744];
int szR[744];
int l[200200];
int r[200200];
int GOOD[2944];
int GG = 0;
int BAD[2944];
int BB = 0;
void add(int id){
	GOOD[GG++] = id;
}
int bad[200200];
void del(int id){
	BAD[BB++] = id;
	bad[id] = 1;
}

bool cmpL(int i, int j){
	if(l[i] != l[j]) return l[i] > l[j];
	return i < j;
}
bool cmpR(int i, int j){
	if(r[i] != r[j]) return r[i] < r[j];
	return i < j;
}
bool cmpG(int i, int j){
	if(r[i] - l[i] != r[j] - l[j]) return r[i] - l[i] > r[j] - l[j];
	return i < j;
}

int was[200200];
int pref[2020];
int T;
int get(int a, int b, int k){
	if(b - a + 1 < k) return 0;
	int I = 1, J = K - 1, c = 1;
	while(I <= J){
		int mid = (I + J)>>1;
		if(szG[mid]>0 && r[G[mid][0]] - l[G[mid][0]] + 1 >= k){
			c = mid;
			I = mid+1;
		}else {
			J = mid-1;
		}
	}

	int ans = pref[c-1];
	I = 1, J = K-1;
	int d = 1;
	while(I <= J){
		int mid = (I + J)>>1;
		if(szR[mid]>0 && r[R[mid][0]] < a + k - 1){
			d = mid;
			I = mid+1;
		}else {
			J = mid-1;
		}
	}
	I = 1, J = K-1;
	int e = 1;
	while(I <= J){
		int mid = (I + J)>>1;
		if(szL[mid]>0 && l[L[mid][0]] > b - k + 1){
			e = mid;
			I = mid+1;
		}else {
			J = mid-1;
		}
	}
	ans -= A[c-1][e-1];
	
	ans -= B[c-1][d-1];
	++T;
	for(int i = 0; i < szG[c]; i++){
		int id = G[c][i];
		if(min(r[id], b) - max(a, l[id]) + 1 >= k) ans++;
	}
	for(int i = 0; i < szL[e]; i++){
		int id = L[e][i];
		if(pos[id] >= c) continue;
		if(R_pos[id] < d) continue;
		if(min(r[id], b) - max(a, l[id]) + 1 < k) --ans;
		was[id] = T;
	}
	for(int i = 0; i < szR[d]; i++){
		int id = R[d][i];
		if(pos[id] >= c || was[id] == T) continue;
		if(L_pos[id] < e) continue;
		if(min(r[id], b) - max(a, l[id]) + 1 < k) --ans;
	}
	for(int i = 0; i < GG; i++){
		int id = GOOD[i];
		if(min(r[id], b) - max(a, l[id]) + 1 >= k) ++ans;
	}
	for(int i = 0; i <BB; i++){
		int id = BAD[i];
		if(min(r[id], b) - max(a, l[id]) + 1 >= k) --ans;
	}
	return ans;
}

int a[200200];
int sz = 0;
void recalc(){
	for(int i = 1; i < K; i++){
		for(int j = 1; j < K; j++){
			A[i][j] = 0;
			B[i][j] = 0;
		}
	}
	
	sz = 0;
	int st = 0;
	sort(GOOD, GOOD + GG, cmpR);
	for(int i = 1; i < K; i++){
		for(int j = 0; j < szR[i];j++) {
			if(bad[R[i][j]]) continue;
			while(st < GG && cmpR(GOOD[st], R[i][j])){
				if(!bad[GOOD[st]]){
					a[sz++] = GOOD[st];
				}
				++st;
			}
			a[sz++] = R[i][j];
		}
		szR[i] = 0;
	}
	while(st < GG){
		if(!bad[GOOD[st]]){
			a[sz++] = GOOD[st];
		}
		++st;
	}
	for(int i = 0 ; i < sz; i++){
		int ind = i/KK + 1;
		R_pos[a[i]] = ind;
		R[ind][szR[ind]++] = a[i];
	}
	sz = 0;

	st = 0;
	sort(GOOD, GOOD + GG, cmpL);
	for(int i = 1; i < K; i++){
		for(int j = 0; j < szL[i];j++) {
			if(bad[L[i][j]]) continue;
			while(st < GG && cmpL(GOOD[st], L[i][j])){
				if(!bad[GOOD[st]]){
					a[sz++] = GOOD[st];
				}
				++st;
			}
			a[sz++] = L[i][j];
		}
		szL[i] = 0;
	}
	while(st < GG){
		if(!bad[GOOD[st]]){
			a[sz++] = GOOD[st];
		}
		++st;
	}
	for(int i = 0 ; i < sz; i++){
		int ind = i/KK + 1;
		L_pos[a[i]] = ind;
		L[ind][szL[ind]++] = a[i];
	}
	sz = 0;
		st = 0;
	sort(GOOD, GOOD + GG, cmpG);
	for(int i = 1; i < K; i++){
		
		for(int j = 0; j < szG[i];j++) {
			if(bad[G[i][j]]) continue;
			while(st < GG && cmpG(GOOD[st], G[i][j])){
				if(!bad[GOOD[st]]){
					a[sz++] = GOOD[st];
				}
				++st;
			}
			a[sz++] = G[i][j];
		}
		szG[i] = 0;
	}
	while(st < GG){
		if(!bad[GOOD[st]]){
			a[sz++] = GOOD[st];
		}
		++st;
	}
	GG = 0;
	BB = 0;
	for(int i = 0; i < sz; i++){
		int ind = i/KK + 1;
		pos[a[i]] = ind;
		G[ind][szG[ind]++] = a[i];
		A[ind][L_pos[a[i]]]++;
		B[ind][R_pos[a[i]]]++;
	}
	K = sz/KK + 2;

	for(int i = 1; i < K; i++){
		for(int j = 1; j < K; j++){
			A[i][j] += A[i][j-1] + A[i-1][j] - A[i-1][j-1];
			B[i][j] += B[i][j-1] + B[i-1][j] - B[i-1][j-1];
		}
	}
	for(int i = 1; i < K; i++){
		pref[i] = pref[i-1] + szG[i];
	}
}
void solve(){
	int q;
	int G;
	scanf("%d%d", &q, &G);
	int id = 1;
	vector<int> ans;
	int last = 0;
	int lastans = 0;
	for(int i = 0, ty, a, b, k; i < q; i++){
		scanf("%d", &ty);
		if(GG + BB == 700) {
			recalc();
		}
		if(ty == 1){
			scanf("%d%d", &l[id], &r[id]);
			l[id] = l[id]^(lastans*G);
			r[id] = r[id]^(lastans*G);
			if(l[id] > r[id]) swap(l[id], r[id]);
			add(id);
			++id;
		}
		else if(ty==2){
			scanf("%d", &a);
			del(a);
		}
		else if(ty == 3){
			scanf("%d%d%d", &a, &b, &k);
			
			a = a^(lastans*G);
			b = b^(lastans*G);
			if(a>b) swap(a, b);
			lastans = get(a, b, k);
			++last;
			ans.pb(lastans);
		}
	}
	forit(it, ans){
		printf("%d\n", *it);
	}
}

int main () {
	#ifdef LOCAL
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	#endif
    int t=1;
    //scanf("%d", &t);
    for(int i=1; i <= t; i++){
      //printf("Case #%d\n", i);
      solve();
    }

    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void solve()':
segments.cpp:263:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &q, &G);
                       ^
segments.cpp:269:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ty);
                   ^
segments.cpp:274:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &l[id], &r[id]);
                                 ^
segments.cpp:282:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
                   ^
segments.cpp:286:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &a, &b, &k);
                               ^

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