oj.uz

Submission #927756

# Submission time Handle Problem Language Result Execution time Memory
927756 2024-02-15T09:57:19 Z cadmiumsky Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 27580 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 theyre out here saying ca daca le tii in map direct e O(N) toata chestia
  #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}];
      }
      
      vector<int> counter_app(sz(Ks));
      
      n = 0;
      for(auto &[a, b] : nrm) b = ++n, atrf[b] = a, fwr[b].sum = fwr[b].own = 0;
      
      for(auto [a, b] : actives) 
        fwr[nrm[pii{a, b}]].own++;
      
      map<int, int> for_links;
      for(int i = n, atrcoef = sz(Ks) - 1; i > 0; atrcoef = (atrcoef == 0? sz(Ks) - 1 : atrcoef - 1), i--) {
        auto [a, b] = atrf[i];
        
        int poz = distance(begin(Ks), prev(upper_bound(all(Ks), b - a + 1)));
        counter_app[poz] += fwr[i].own;
        
        fwr[i].link = atrcoef;
        fwr[i].sum = counter_app[atrcoef];
        
        fwrpoz.emplace(pii{a, i});
        
        //cerr << a << ' ' << b << '\t' << fwr[i].link << ' ' << ;
      }
    }
    // ---- 
    
    { // 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) {
    k = norm_Ks[k];
    auto it = fwrpoz.upper_bound(pii{R, - 1});
    if(it == fwrpoz.end()) return 0;
    
    int poz = it -> second;
    int rez = 0;
    while(k < sz(currKs) && poz <= n) {
      if(fwr[poz].link == k) {
        rez += fwr[poz].sum;
        k++;
      }
      
      if(k < sz(currKs) && currKs[k] <= atrf[poz].second - atrf[poz].first + 1) rez += fwr[poz].own;
      poz++;
    }
    return rez;
  }
} 

//#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 theyre out here saying ca daca le tii in map direct e O(N) toata chestia [-Wcpp]
   42 |   #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia
      |    ^~~~~~~
segments.cpp:43:4: warning: #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) [-Wcpp]
   43 |   #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 8796 KB Output is correct
4 Correct 7 ms 8796 KB Output is correct
5 Correct 234 ms 9564 KB Output is correct
6 Correct 302 ms 9560 KB Output is correct
7 Correct 186 ms 8928 KB Output is correct
8 Correct 475 ms 9432 KB Output is correct
9 Correct 507 ms 9372 KB Output is correct
10 Correct 222 ms 9820 KB Output is correct
11 Correct 384 ms 9556 KB Output is correct
12 Correct 379 ms 9396 KB Output is correct
13 Correct 237 ms 10044 KB Output is correct
14 Correct 458 ms 9304 KB Output is correct
15 Correct 6 ms 8792 KB Output is correct
16 Correct 18 ms 8816 KB Output is correct
17 Correct 378 ms 9072 KB Output is correct
18 Correct 320 ms 9696 KB Output is correct
19 Correct 362 ms 9112 KB Output is correct
20 Correct 378 ms 9048 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 10592 KB Output is correct
2 Correct 260 ms 10324 KB Output is correct
3 Correct 2395 ms 10648 KB Output is correct
4 Correct 358 ms 10320 KB Output is correct
5 Execution timed out 5022 ms 26092 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 10492 KB Output is correct
2 Correct 364 ms 10116 KB Output is correct
3 Correct 341 ms 10316 KB Output is correct
4 Correct 588 ms 10572 KB Output is correct
5 Execution timed out 5011 ms 27580 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 8796 KB Output is correct
4 Correct 7 ms 8796 KB Output is correct
5 Correct 234 ms 9564 KB Output is correct
6 Correct 302 ms 9560 KB Output is correct
7 Correct 186 ms 8928 KB Output is correct
8 Correct 475 ms 9432 KB Output is correct
9 Correct 507 ms 9372 KB Output is correct
10 Correct 222 ms 9820 KB Output is correct
11 Correct 384 ms 9556 KB Output is correct
12 Correct 379 ms 9396 KB Output is correct
13 Correct 237 ms 10044 KB Output is correct
14 Correct 458 ms 9304 KB Output is correct
15 Correct 6 ms 8792 KB Output is correct
16 Correct 18 ms 8816 KB Output is correct
17 Correct 378 ms 9072 KB Output is correct
18 Correct 320 ms 9696 KB Output is correct
19 Correct 362 ms 9112 KB Output is correct
20 Correct 378 ms 9048 KB Output is correct
21 Execution timed out 5021 ms 21452 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 8796 KB Output is correct
4 Correct 7 ms 8796 KB Output is correct
5 Correct 234 ms 9564 KB Output is correct
6 Correct 302 ms 9560 KB Output is correct
7 Correct 186 ms 8928 KB Output is correct
8 Correct 475 ms 9432 KB Output is correct
9 Correct 507 ms 9372 KB Output is correct
10 Correct 222 ms 9820 KB Output is correct
11 Correct 384 ms 9556 KB Output is correct
12 Correct 379 ms 9396 KB Output is correct
13 Correct 237 ms 10044 KB Output is correct
14 Correct 458 ms 9304 KB Output is correct
15 Correct 6 ms 8792 KB Output is correct
16 Correct 18 ms 8816 KB Output is correct
17 Correct 378 ms 9072 KB Output is correct
18 Correct 320 ms 9696 KB Output is correct
19 Correct 362 ms 9112 KB Output is correct
20 Correct 378 ms 9048 KB Output is correct
21 Execution timed out 5021 ms 21452 KB Time limit exceeded
22 Halted 0 ms 0 KB -