Submission #50909

#	Time	Username	Problem	Language	Result	Execution time	Memory
50909		Nicksechko	Segments (IZhO18_segments)	C++14	75 / 100	3520 ms	120052 KiB

segments

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
 
#define mp make_pair
#define pb push_back
 
 
typedef long long ll;
typedef long double ld;

#define f first
#define s second
 
using namespace std;

const int N = 1e5 + 123;

int q, n, id, l[N], r[N];
bool used[N];

vector < pair < int, pair < int, int > > > lazy; 

vector < int > L[265000], R[265000];

vector < pair < int, int > > segments;

void build(int v = 1, int tl = 0, int tr = n - 1) {
  if (tl > tr) return;
  if (tl == tr) {
    L[v].clear();
    R[v].clear();
    if (tl < segments.size()) {
      L[v].push_back(segments[tl].first);
      R[v].push_back(segments[tl].second);
    }
    return;
  }
  int tm = (tl + tr) / 2;
  build(v * 2, tl, tm);
  build(v * 2 + 1, tm + 1, tr);
  L[v].resize(L[v * 2].size() + L[v * 2 + 1].size());
  R[v].resize(R[v * 2].size() + R[v * 2 + 1].size());
  merge(L[v * 2].begin(), L[v * 2].end(), L[v * 2 + 1].begin(), L[v * 2 + 1].end(), L[v].begin());
  merge(R[v * 2].begin(), R[v * 2].end(), R[v * 2 + 1].begin(), R[v * 2 + 1].end(), R[v].begin());  
}

int getId(int k) {
  int ans = -1, l = 0, r = segments.size() - 1;
  while(l <= r) {
    int mid = (l + r) / 2;
    int len = segments[mid].second - segments[mid].first + 1;
    if (len >= k) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
}

int get(int l, int r, int A, int B, int k, int v = 1, int tl = 0, int tr = n - 1) {
  if (tl > r || tr < l || l > r || tl > tr) return 0;
  if (l <= tl && tr <= r) {
    int res = (lower_bound(R[v].begin(), R[v].end(), A + k - 1) - R[v].begin())
            + (L[v].end() - upper_bound(L[v].begin(), L[v].end(), B - k + 1));
    return res;
  }
  int tm = (tl + tr) / 2;
  int ans = get(l, r, A, B, k, v * 2, tl, tm) + get(l, r, A, B, k, v * 2 + 1, tm + 1, tr);
  return ans;
}

int inter(int l1, int r1, int l2, int r2) {
  return max(0, min(r1, r2) - max(l1, l2) + 1);
}

int query(int A, int B, int k) {
  if (B - A + 1 < k) return 0;
  int id = getId(k);
  int ans = id + 1 - get(0, id, A, B, k);
  for (auto i : lazy) {
    if (inter(i.second.first, i.second.second, A, B) >= k) {
      if (i.first == 1) ans++;
      else ans--;
    }  
  }
  return ans;
}

bool cmp(pair < int, int > a, pair < int, int > b) {
  return a.second - a.first + 1 > b.second - b.first + 1;
}

void rebuild() {
  segments.clear();
  lazy.clear();
  for (int i = 1;i <= id;i++) {
    if (!used[i]) {
      segments.pb({l[i], r[i]});
    }
  }
  sort(segments.begin(), segments.end(), &cmp);
  n = 1;
  while(n < segments.size()) n *= 2;
  build();
}

int main() {
//	freopen("input", "r", stdin);
//	freopen("output", "w", stdout);
  int G;
  scanf("%d%d", &q, &G);
  int K = sqrt(q * 19);
  int lst_ans = 0;
  //cout << q << " " << K << endl;
  for (int i = 0, t, x, was = 0;i < q;i++) {
  	if (i % K == 0) {
//  		cout << "starting\n";
  		rebuild();
  //		cout << "Succesfully i = " << i / K << endl;
  	}
    scanf("%d", &t);
    if (t == 1) {
      id++;
      scanf("%d%d", &l[id], &r[id]);
      l[id] = l[id] ^ (G * lst_ans);
      r[id] = r[id] ^ (G * lst_ans);
      if (l[id] > r[id]) swap(l[id], r[id]);
      lazy.push_back({1, {l[id], r[id]}});
    }
    if (t == 2) {
    	scanf("%d", &x);
    	used[x] = 1;
    	lazy.push_back({2, {l[x], r[x]}});
    }
    if (t == 3) {
      int a, b, k;
      scanf("%d%d%d", &a, &b, &k);
      a = a ^ (G * lst_ans);
      b = b ^ (G * lst_ans);
      if (a > b) swap(a, b);
      printf("%d\n", lst_ans = query(a, b, k));
    }
  }
  return 0;
}
 
 

Compilation message (stderr)

segments.cpp: In function 'void build(int, int, int)':
segments.cpp:43:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (tl < segments.size()) {
         ~~~^~~~~~~~~~~~~~~~~
segments.cpp: In function 'void rebuild()':
segments.cpp:116:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n < segments.size()) n *= 2;
         ~~^~~~~~~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:128:25: warning: unused variable 'was' [-Wunused-variable]
   for (int i = 0, t, x, was = 0;i < q;i++) {
                         ^~~
segments.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &q, &G);
   ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
segments.cpp:137:12: 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:144:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &x);
      ~~~~~^~~~~~~~~~
segments.cpp:150:12: 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: 0 / 25