Submission #391779

#	Time	Username	Problem	Language	Result	Execution time	Memory
391779		BartolM	Segments (IZhO18_segments)	C++17	16 / 100	2271 ms	5464 KiB

segments

#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int SIZ=500;
const int CNT=1000;
const int REB=500;
const int N=2e5+5;
#warning limiti

int q, t, id=1, n=0, buc=1, lastans=0;
pii p[N];
vector <int> R[CNT], L[CNT], v[CNT], pom;
int maxi[CNT];

int cmp(int a, int b) {
    return p[a].Y-p[a].X<p[b].Y-p[b].X;
}

void xoraj(int &x) {
    x=x^(t*lastans);
}

void dodaj(pii pp) {
    int d=pp.Y-pp.X+1;
    for (int i=0; i<buc; ++i) {
        if (i!=buc-1 && maxi[i]<d) continue;
        v[i].pb(id);
        L[i].insert(lower_bound(L[i].begin(), L[i].end(), pp.X), pp.X);
        R[i].insert(lower_bound(R[i].begin(), R[i].end(), pp.Y), pp.Y);
        maxi[i]=max(maxi[i], d);
        break;
    }
    p[id++]=pp; n++;
}

void obrisi(int ind) {
    n--; pii pp=p[ind];
    for (int i=0; i<buc; ++i) {
        if (maxi[i]<pp.Y-pp.X+1) continue;
        L[i].erase(lower_bound(L[i].begin(), L[i].end(), pp.X));
        R[i].erase(lower_bound(R[i].begin(), R[i].end(), pp.Y));
        int iz=-1;
        for (int j=0; j<v[i].size(); ++j) if (v[i][j]==ind) iz=j;
        assert(iz!=-1);
        v[i].erase(v[i].begin()+iz);
        break;
    }
}

void rebuild() {
    pom.clear();
    for (int i=0; i<buc; ++i) {
        for (int x:v[i]) pom.pb(x);
        v[i].clear();
        L[i].clear();
        R[i].clear();
        maxi[i]=0;
    }
    sort(pom.begin(), pom.end(), cmp);
    buc=1;
    for (int x:pom) {
        if (v[buc-1].size()>=SIZ) buc++;
        maxi[buc-1]=p[x].Y-p[x].X+1;
        v[buc-1].pb(x);
        L[buc-1].pb(p[x].X); R[buc-1].pb(p[x].Y);
    }
    for (int i=0; i<buc; ++i) sort(L[i].begin(), L[i].end()), sort(R[i].begin(), R[i].end());
}

int query(int l, int r, int k) {
    int prvi=1, losi=0;
    for (int i=0; i<buc; ++i) {
        if (maxi[i]<k) {
            losi+=(int)v[i].size();
            continue;
        }
        if (prvi) {
            for (int x:v[i]) losi+=(p[x].Y<l+k-1) || (p[x].X>r-k+1);
            prvi=0;
        }
        else {
            losi+=L[i].end()-upper_bound(L[i].begin(), L[i].end(), r-k+1);
            losi+=lower_bound(R[i].begin(), R[i].end(), l+k-1)-R[i].begin();
        }
    }
    return n-losi;
}

int main() {
    scanf("%d %d", &q, &t);
    for (int i=0; i<q; ++i) {
        int tip, l, r, k;
        scanf("%d", &tip);
        if (tip==1) {
            scanf("%d %d", &l, &r); xoraj(l); xoraj(r);
            if (l>r) swap(l, r);
            dodaj(mp(l, r));
        }
        else if (tip==2) {
            scanf("%d", &k);
            obrisi(k);
        }
        else {
            scanf("%d %d %d", &l, &r, &k); xoraj(l); xoraj(r);
            if (l>r) swap(l, r);
            lastans=query(l, r, k);
            printf("%d\n", lastans);
        }
        if (i%SIZ==0 && i) rebuild();
    }
	return 0;
}

Compilation message (stderr)

segments.cpp:21:2: warning: #warning limiti [-Wcpp]
   21 | #warning limiti
      |  ^~~~~~~
segments.cpp: In function 'void obrisi(int)':
segments.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j=0; j<v[i].size(); ++j) if (v[i][j]==ind) iz=j;
      |                       ~^~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d %d", &q, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |         scanf("%d", &tip);
      |         ~~~~~^~~~~~~~~~~~
segments.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |             scanf("%d %d", &l, &r); xoraj(l); xoraj(r);
      |             ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |             scanf("%d", &k);
      |             ~~~~~^~~~~~~~~~
segments.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |             scanf("%d %d %d", &l, &r, &k); xoraj(l); xoraj(r);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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