Submission #927318

#	Time	Username	Problem	Language	Result	Execution time	Memory
927318		cadmiumsky	Segments (IZhO18_segments)	C++17	0 / 100	228 ms	65536 KiB

segments

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;

pii segments[nmax];

struct Oper {
  int type;
  int a, b;
  int k;
};

namespace Precalc {
  
  multiset<pii> actives;
  
  void rebatch(vector<Oper> opqueue) {
    for(auto [t, a, b, k] : opqueue) {
      if(t == 1)
        actives.insert(pii{a, b});
      else if(t == 2)
        actives.erase(actives.find(segments[a]));
    }
    
    return;
  }
  struct Item {
    int link, sum;
  };
  
  #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
  set<pii> fwrpoz[nmax];
  set<pii> bckwpoz[nmax];
  int freq[nmax];
  Item fwr[nmax], bckw[nmax];
  pii atrf[nmax], atrb[nmax];
  map<int, int> norm_Ks;
  
  int n;
  
  void contextualize(vector<int> Ks) {
    norm_Ks.clear();
    for(auto x : Ks) norm_Ks[x];
    int ptrnrm = 0;
    for(auto &[a, b] : norm_Ks) b = ptrnrm++;
    for(auto x : Ks) fwrpoz[norm_Ks[x]].clear(), bckwpoz[norm_Ks[x]].clear(), freq[norm_Ks[x]] = 0;
    
    { // forward links
      map<pii, int> nrm;
      
      for(auto [a, b] : actives) {
        int k = b - a + 1;
        if(k < Ks[0]) continue;
        nrm[pii{a, b}];
      }
      
      n = 0;
      for(auto &[a, b] : nrm) b = ++n, atrf[b] = a, fwr[b].sum = 0;
      
      for(auto [a, b] : actives) 
        fwr[nrm[pii{a, b}]].sum++;
      
      map<int, int> for_links;
      for(int i = n; i > 0; i--) {
        auto [a, b] = atrf[i];
        int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1)));
        
        if(for_links.count(Ks[poz]) == 0);
        else fwr[i].sum += fwr[for_links[Ks[poz]]].sum;
        
        if(poz == sz(Ks) - 1 || for_links.count(Ks[poz + 1]) == 0) fwr[i].link = n + 1;
        else fwr[i].link = for_links[Ks[poz + 1]];
        for_links[Ks[poz]] = i;
        fwrpoz[poz].emplace(pii{a, i});
      }
    }
    // ---- 
    
    { // backward links
      auto cmp = [](const pii& a, const pii& b) -> bool { return a.second < b.second || (a.second == b.second && a.first < b.first); };
      map<pii, int, decltype(cmp)> nrm(cmp);
      
      for(auto [a, b] : actives) {
        int k = b - a + 1;
        if(k < Ks[0]) continue;
        nrm[pii{a, b}];
      }
      
      n = 0;
      for(auto &[a, b] : nrm) b = ++n, atrb[b] = a, bckw[b].sum = 0;
      
      for(auto [a, b] : actives) 
        bckw[nrm[pii{a, b}]].sum++;
      
      map<int, int> for_links;
      for(int i = 1; i <= n; i++) {
        auto [a, b] = atrb[i];
        int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1)));
        
        if(for_links.count(Ks[poz]) == 0);
        else bckw[i].sum += bckw[for_links[Ks[poz]]].sum;
        
        if(poz == sz(Ks) - 1 || for_links.count(Ks[poz + 1]) == 0) bckw[i].link = n + 1;
        else bckw[i].link = for_links[Ks[poz + 1]];
        
        for_links[Ks[poz]] = i;
        bckwpoz[poz].emplace(pii{b, i});
      }
    }
      
    for(auto [a, b] : actives) {
      int k = b - a + 1;
      if(k < Ks[0]) continue;
      freq[distance(begin(Ks), prev(upper_bound(all(Ks), k)))]++;
    }
    
    for(int i = sz(Ks) - 2; i >= 0; i--)
      freq[i] += freq[i + 1];
  }
  
  int query_K(int k) { 
    return freq[norm_Ks[k]];
  }
  int query_L(int L, int k) {
    int p = norm_Ks[k];
    auto it = bckwpoz[p].upper_bound(pii{L + 1, - 1});
    if(it == bckwpoz[p].begin()) return 0;
    
    int poz = prev(it) -> second;
    int rez = 0;
    while(poz > 0) {
      rez += bckw[poz].sum;
      assert(bckw[poz].link < poz);
      poz = bckw[poz].link;
    }
    return rez;
  }
  
  int query_R(int R, int k) {
    int cnt = 0;
    for(auto [a, b] : actives) cnt += (b - a + 1 >= k) && (a >= R);
    return cnt;
  }
}

int segmpoz = 1;

int unitValue(int l, int r, int a, int b, int k) {
  return min(r, b) - max(l, a) + 1 >= k;
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, t_offline;
  cin >> n >> t_offline;
  
  const int idealBuck = min(5., ceil(sqrt(n * log2(n))));
  const ll worstInner = (ll)ceil(idealBuck / 2) * ceil(idealBuck / 2) + 5;
  
  
  vector<Oper> operation_queue;

  int lastans = 0;
  
  auto flush_queue = [&]() {
    vector<int> Ks;
    for(auto [t, a, b, k] : operation_queue)
      if(t == 3) Ks.emplace_back(k);
    
    sort(all(Ks));
    Ks.erase(unique(all(Ks)), Ks.end());
    
    Precalc::contextualize(Ks);
    
    for(int i = 0; i < sz(operation_queue); i++) {
      auto &[ti, ai, bi, ki] = operation_queue[i];
      if(ti == 1 || ti == 3) {
        ai = ai ^ (t_offline * lastans);
        bi = bi ^ (t_offline * lastans);
        if(ai > bi) swap(ai, bi);
      }
      
      if(ti == 1)
        segments[segmpoz++] = pii{ai, bi};
      
      if(ti == 3) {
        if(bi - ai + 1 < ki) {
          lastans = 0;
        }
        else {
          int rez = Precalc::query_K(ki) - Precalc::query_R(bi - ki + 1 + 1, ki) - Precalc::query_L(ai + ki - 1 - 1, ki);
          //cerr << "? " << ai << ' ' << bi << '\t' << rez << '\n';
          for(int j = i - 1; j >= 0; j--) {
            auto &[tj, aj, bj, kj] = operation_queue[j];
            
            if(tj == 3) continue;
            
            //cerr << tj << aj << ' ' << bj << '\n';
            else if(tj == 2)
              rez -= unitValue(ai, bi, segments[aj].first, segments[aj].second, ki);
            else
              rez += unitValue(ai, bi, aj, bj, ki);
          }
          lastans = rez;
        }
        cout << lastans << '\n';
      }
    }
    
    Precalc::rebatch(operation_queue);
    operation_queue.clear();
  };
  int cnt[2] = {1, 0};
  
  for(int t, a, b, k, tc = 0; tc < n; tc++) {
    cin >> t;
    if(t == 1) {
       cin >> a >> b;
       operation_queue.emplace_back(Oper{t, a, b, -1});
       cnt[0]++;
    }
    if(t == 2) {
       cin >> a;
       operation_queue.emplace_back(Oper{t, a, -1, -1});
       cnt[0]++;
    }
    if(t == 3) {
       cin >> a >> b >> k;
       operation_queue.emplace_back(Oper{t, a, b, k});
       cnt[1]++;
    }
    
    if(tc == n - 1 || (ll)cnt[0] * cnt[1] >= worstInner) {
      flush_queue();
      
      cnt[0] = 1;
      cnt[1] = 0;
    }
  }
  
  return 0;
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/

Compilation message (stderr)

segments.cpp:42:4: warning: #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) [-Wcpp]
   42 |   #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
      |    ^~~~~~~

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