oj.uz

Submission #927773

# Submission time Handle Problem Language Result Execution time Memory
927773 2024-02-15T10:24:40 Z cadmiumsky Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 28704 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;
  
  multiset<pii> actives_sortfwr;
  auto cmp = [](const pii& a, const pii& b) -> bool { return a.second < b.second || (a.second == b.second && a.first < b.first); };
  multiset<pii, decltype(cmp)> actives_sortbckw(cmp);
  
  void rebatch(vector<Oper> opqueue) {
    for(auto [t, a, b, k] : opqueue) {
      if(t == 1)
        actives.insert(pii{a, b}),
        actives_sortfwr.insert(pii{a, b}),
        actives_sortbckw.insert(pii{a, b});
      else if(t == 2)
        actives.erase(actives.find(segments[a])),
        actives_sortfwr.erase(actives_sortfwr.find(segments[a])),
        actives_sortbckw.erase(actives_sortbckw.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) freq[ptrnrm] = 0, b = ptrnrm++;
    
    fwrpoz.clear(), bckwpoz.clear();
    
    { // forward links
      pii lst = {-1, -1};
      
      n = 0;
      for(auto [a, b] : actives_sortfwr) {
        int k = b - a + 1;
        if(k < Ks[0]) continue;
        if(pii{a, b} != lst) n++;
        atrf[n] = lst = pii{a, b};
        fwr[n].sum = fwr[n].own = 0;
      }
      
      lst = {-1, -1};
      n = 0;
      for(auto [a, b] : actives_sortfwr) {
        int k = b - a + 1;
        if(k < Ks[0]) continue;
        if(pii{a, b} != lst) n++;
        fwr[n].own++;
        lst = pii{a, b};
      }
      vector<int> counter_app(sz(Ks));
      
      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});
      }
    }
    // ---- 
    
    { // backward links
      pii lst = {-1, -1};
      
      n = 0;
      for(auto [a, b] : actives_sortbckw) {
        int k = b - a + 1;
        if(k < Ks[0]) continue;
        if(pii{a, b} != lst) n++;
        atrb[n] = lst = pii{a, b};
        bckw[n].sum = bckw[n].own = 0;
      }
      
      lst = {-1, -1};
      n = 0;
      for(auto [a, b] : actives_sortbckw) {
        int k = b - a + 1;
        if(k < Ks[0]) continue;
        if(pii{a, b} != lst) n++;
        bckw[n].own++;
        lst = pii{a, b};
      }
      
      vector<int> counter_app(sz(Ks));
      
      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 || sz(operation_queue) >= idealBuck) {
      flush_queue();
      
      cnt[0] = 1;
      cnt[1] = 0;
    }
  }
  
  return 0;
}

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

Compilation message

segments.cpp:50:4: warning: #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia [-Wcpp]
   50 |   #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia
      |    ^~~~~~~
segments.cpp:51:4: warning: #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) [-Wcpp]
   51 |   #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv)
      |    ^~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:213:12: warning: unused variable 'worstInner' [-Wunused-variable]
  213 |   const ll worstInner = (ll)ceil(idealBuck / 2) * ceil(idealBuck / 2) + 5;
      |            ^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 7 ms 8664 KB Output is correct
4 Correct 6 ms 8692 KB Output is correct
5 Correct 175 ms 9564 KB Output is correct
6 Correct 216 ms 9564 KB Output is correct
7 Correct 82 ms 8792 KB Output is correct
8 Correct 224 ms 9304 KB Output is correct
9 Correct 229 ms 9352 KB Output is correct
10 Correct 121 ms 10096 KB Output is correct
11 Correct 270 ms 9304 KB Output is correct
12 Correct 273 ms 9308 KB Output is correct
13 Correct 116 ms 9820 KB Output is correct
14 Correct 210 ms 9308 KB Output is correct
15 Correct 6 ms 8536 KB Output is correct
16 Correct 11 ms 8540 KB Output is correct
17 Correct 152 ms 9044 KB Output is correct
18 Correct 158 ms 9720 KB Output is correct
19 Correct 162 ms 9048 KB Output is correct
20 Correct 213 ms 9052 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 9048 KB Output is correct
2 Correct 157 ms 9016 KB Output is correct
3 Correct 1000 ms 9100 KB Output is correct
4 Correct 214 ms 9196 KB Output is correct
5 Execution timed out 5055 ms 27620 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 8788 KB Output is correct
2 Correct 207 ms 9140 KB Output is correct
3 Correct 189 ms 8956 KB Output is correct
4 Correct 302 ms 8952 KB Output is correct
5 Execution timed out 5035 ms 28704 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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 7 ms 8664 KB Output is correct
4 Correct 6 ms 8692 KB Output is correct
5 Correct 175 ms 9564 KB Output is correct
6 Correct 216 ms 9564 KB Output is correct
7 Correct 82 ms 8792 KB Output is correct
8 Correct 224 ms 9304 KB Output is correct
9 Correct 229 ms 9352 KB Output is correct
10 Correct 121 ms 10096 KB Output is correct
11 Correct 270 ms 9304 KB Output is correct
12 Correct 273 ms 9308 KB Output is correct
13 Correct 116 ms 9820 KB Output is correct
14 Correct 210 ms 9308 KB Output is correct
15 Correct 6 ms 8536 KB Output is correct
16 Correct 11 ms 8540 KB Output is correct
17 Correct 152 ms 9044 KB Output is correct
18 Correct 158 ms 9720 KB Output is correct
19 Correct 162 ms 9048 KB Output is correct
20 Correct 213 ms 9052 KB Output is correct
21 Execution timed out 5050 ms 21980 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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 7 ms 8664 KB Output is correct
4 Correct 6 ms 8692 KB Output is correct
5 Correct 175 ms 9564 KB Output is correct
6 Correct 216 ms 9564 KB Output is correct
7 Correct 82 ms 8792 KB Output is correct
8 Correct 224 ms 9304 KB Output is correct
9 Correct 229 ms 9352 KB Output is correct
10 Correct 121 ms 10096 KB Output is correct
11 Correct 270 ms 9304 KB Output is correct
12 Correct 273 ms 9308 KB Output is correct
13 Correct 116 ms 9820 KB Output is correct
14 Correct 210 ms 9308 KB Output is correct
15 Correct 6 ms 8536 KB Output is correct
16 Correct 11 ms 8540 KB Output is correct
17 Correct 152 ms 9044 KB Output is correct
18 Correct 158 ms 9720 KB Output is correct
19 Correct 162 ms 9048 KB Output is correct
20 Correct 213 ms 9052 KB Output is correct
21 Execution timed out 5050 ms 21980 KB Time limit exceeded
22 Halted 0 ms 0 KB -