oj.uz

Submission #927771

# Submission time Handle Problem Language Result Execution time Memory
927771 2024-02-15T10:20:14 Z cadmiumsky Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 33644 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
      map<pii, int> nrm;
      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
      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 || 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:209:12: warning: unused variable 'worstInner' [-Wunused-variable]
  209 |   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 3 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 7 ms 8540 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 341 ms 10068 KB Output is correct
6 Correct 440 ms 9888 KB Output is correct
7 Correct 168 ms 9120 KB Output is correct
8 Correct 470 ms 9856 KB Output is correct
9 Correct 518 ms 9512 KB Output is correct
10 Correct 222 ms 10112 KB Output is correct
11 Correct 560 ms 9488 KB Output is correct
12 Correct 551 ms 9504 KB Output is correct
13 Correct 226 ms 10072 KB Output is correct
14 Correct 440 ms 9472 KB Output is correct
15 Correct 6 ms 8540 KB Output is correct
16 Correct 17 ms 8720 KB Output is correct
17 Correct 322 ms 9088 KB Output is correct
18 Correct 321 ms 10208 KB Output is correct
19 Correct 351 ms 9048 KB Output is correct
20 Correct 407 ms 9192 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 9276 KB Output is correct
2 Correct 255 ms 9040 KB Output is correct
3 Correct 2201 ms 9328 KB Output is correct
4 Correct 329 ms 9040 KB Output is correct
5 Execution timed out 5050 ms 31844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 9040 KB Output is correct
2 Correct 334 ms 8932 KB Output is correct
3 Correct 311 ms 9040 KB Output is correct
4 Correct 548 ms 9312 KB Output is correct
5 Execution timed out 5025 ms 33644 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 7 ms 8540 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 341 ms 10068 KB Output is correct
6 Correct 440 ms 9888 KB Output is correct
7 Correct 168 ms 9120 KB Output is correct
8 Correct 470 ms 9856 KB Output is correct
9 Correct 518 ms 9512 KB Output is correct
10 Correct 222 ms 10112 KB Output is correct
11 Correct 560 ms 9488 KB Output is correct
12 Correct 551 ms 9504 KB Output is correct
13 Correct 226 ms 10072 KB Output is correct
14 Correct 440 ms 9472 KB Output is correct
15 Correct 6 ms 8540 KB Output is correct
16 Correct 17 ms 8720 KB Output is correct
17 Correct 322 ms 9088 KB Output is correct
18 Correct 321 ms 10208 KB Output is correct
19 Correct 351 ms 9048 KB Output is correct
20 Correct 407 ms 9192 KB Output is correct
21 Execution timed out 5009 ms 24868 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 7 ms 8540 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 341 ms 10068 KB Output is correct
6 Correct 440 ms 9888 KB Output is correct
7 Correct 168 ms 9120 KB Output is correct
8 Correct 470 ms 9856 KB Output is correct
9 Correct 518 ms 9512 KB Output is correct
10 Correct 222 ms 10112 KB Output is correct
11 Correct 560 ms 9488 KB Output is correct
12 Correct 551 ms 9504 KB Output is correct
13 Correct 226 ms 10072 KB Output is correct
14 Correct 440 ms 9472 KB Output is correct
15 Correct 6 ms 8540 KB Output is correct
16 Correct 17 ms 8720 KB Output is correct
17 Correct 322 ms 9088 KB Output is correct
18 Correct 321 ms 10208 KB Output is correct
19 Correct 351 ms 9048 KB Output is correct
20 Correct 407 ms 9192 KB Output is correct
21 Execution timed out 5009 ms 24868 KB Time limit exceeded
22 Halted 0 ms 0 KB -