oj.uz

Submission #927711

# Submission time Handle Problem Language Result Execution time Memory
927711 2024-02-15T09:15:25 Z cadmiumsky Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 28204 KB 
#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, own;
  };
  
  #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
  set<pii> fwrpoz;
  set<pii> bckwpoz;
  int freq[nmax];
  Item fwr[nmax], bckw[nmax];
  pii atrf[nmax], atrb[nmax];
  map<int, int> norm_Ks;
  vector<int> currKs;
  
  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++;
    
    fwrpoz.clear(), bckwpoz.clear();
    for(auto x : Ks) 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.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}];
      }
      
      vector<int> counter_app(sz(Ks));
      
      n = 0;
      for(auto &[a, b] : nrm) b = ++n, atrb[b] = a, bckw[b].sum = bckw[b].own = 0;
      
      for(auto [a, b] : actives) 
        bckw[nrm[pii{a, b}]].own++;
      
      map<int, int> for_links;
      for(int i = 1, atrcoef = sz(Ks) - 1; i <= n; atrcoef = (atrcoef == 0? sz(Ks) - 1 : atrcoef - 1), i++) {
        auto [a, b] = atrb[i];
        
        int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1)));
        counter_app[poz] += bckw[i].own;
        
        bckw[i].link = atrcoef;
        bckw[i].sum = counter_app[atrcoef];
        
        bckwpoz.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];
    currKs = move(Ks);
    
  }
  
  int query_K(int k) { 
    return freq[norm_Ks[k]];
  }
  int query_L(int L, int k) {
    k = norm_Ks[k];
    auto it = bckwpoz.upper_bound(pii{L + 1, - 1});
    if(it == bckwpoz.begin()) return 0;
    
    int poz = prev(it) -> second;
    int rez = 0;
    while(k < sz(currKs) && poz > 0) {
      if(bckw[poz].link == k) {
        rez += bckw[poz].sum;
        k++;
      }
      
      if(k < sz(currKs) && currKs[k] <= atrb[poz].second - atrb[poz].first + 1) rez += bckw[poz].own;
      poz--;
    }
    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;
  }
} 

//#error in loc sa ai pozitii care corespund unor segmente bune, doar pune suma partiala a alora congruenti cu (-pozitia) mod sz(Ks)

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);
    
    if(sz(Ks) == 0) return;
    
    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);
          for(int j = i - 1; j >= 0; j--) {
            auto &[tj, aj, bj, kj] = operation_queue[j];
            
            if(tj == 3) continue;
            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

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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 7 ms 8792 KB Output is correct
4 Correct 7 ms 8796 KB Output is correct
5 Correct 268 ms 9756 KB Output is correct
6 Correct 341 ms 9928 KB Output is correct
7 Correct 195 ms 8928 KB Output is correct
8 Correct 498 ms 9552 KB Output is correct
9 Correct 511 ms 9388 KB Output is correct
10 Correct 231 ms 10064 KB Output is correct
11 Correct 432 ms 9308 KB Output is correct
12 Correct 433 ms 9392 KB Output is correct
13 Correct 247 ms 9796 KB Output is correct
14 Correct 479 ms 9348 KB Output is correct
15 Correct 8 ms 8664 KB Output is correct
16 Correct 19 ms 8792 KB Output is correct
17 Correct 358 ms 9072 KB Output is correct
18 Correct 334 ms 9816 KB Output is correct
19 Correct 372 ms 9116 KB Output is correct
20 Correct 403 ms 9144 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5023 ms 21348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 10804 KB Output is correct
2 Correct 282 ms 10884 KB Output is correct
3 Correct 2479 ms 11216 KB Output is correct
4 Correct 383 ms 10888 KB Output is correct
5 Execution timed out 5053 ms 26844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 11088 KB Output is correct
2 Correct 396 ms 11088 KB Output is correct
3 Correct 352 ms 11096 KB Output is correct
4 Correct 653 ms 11012 KB Output is correct
5 Execution timed out 5031 ms 28204 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 7 ms 8792 KB Output is correct
4 Correct 7 ms 8796 KB Output is correct
5 Correct 268 ms 9756 KB Output is correct
6 Correct 341 ms 9928 KB Output is correct
7 Correct 195 ms 8928 KB Output is correct
8 Correct 498 ms 9552 KB Output is correct
9 Correct 511 ms 9388 KB Output is correct
10 Correct 231 ms 10064 KB Output is correct
11 Correct 432 ms 9308 KB Output is correct
12 Correct 433 ms 9392 KB Output is correct
13 Correct 247 ms 9796 KB Output is correct
14 Correct 479 ms 9348 KB Output is correct
15 Correct 8 ms 8664 KB Output is correct
16 Correct 19 ms 8792 KB Output is correct
17 Correct 358 ms 9072 KB Output is correct
18 Correct 334 ms 9816 KB Output is correct
19 Correct 372 ms 9116 KB Output is correct
20 Correct 403 ms 9144 KB Output is correct
21 Execution timed out 5023 ms 21348 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 7 ms 8792 KB Output is correct
4 Correct 7 ms 8796 KB Output is correct
5 Correct 268 ms 9756 KB Output is correct
6 Correct 341 ms 9928 KB Output is correct
7 Correct 195 ms 8928 KB Output is correct
8 Correct 498 ms 9552 KB Output is correct
9 Correct 511 ms 9388 KB Output is correct
10 Correct 231 ms 10064 KB Output is correct
11 Correct 432 ms 9308 KB Output is correct
12 Correct 433 ms 9392 KB Output is correct
13 Correct 247 ms 9796 KB Output is correct
14 Correct 479 ms 9348 KB Output is correct
15 Correct 8 ms 8664 KB Output is correct
16 Correct 19 ms 8792 KB Output is correct
17 Correct 358 ms 9072 KB Output is correct
18 Correct 334 ms 9816 KB Output is correct
19 Correct 372 ms 9116 KB Output is correct
20 Correct 403 ms 9144 KB Output is correct
21 Execution timed out 5023 ms 21348 KB Time limit exceeded
22 Halted 0 ms 0 KB -