oj.uz

Submission #927785

# Submission time Handle Problem Language Result Execution time Memory
927785 2024-02-15T10:41:07 Z cadmiumsky Segments (IZhO18_segments) C++17
23 / 100
 5000 ms 33276 KB 
#pragma GCC optimize("Ofast")
#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++; fwr[n].sum = fwr[n].own = 0; }
        atrf[n] = lst = pii{a, b};
        fwr[n].own++;
      }
      
      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++; bckw[n].sum = bckw[n].own = 0; }
        atrb[n] = lst = pii{a, b};
        bckw[n].own++;
      }
      
      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 = 1024;
  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:51:4: warning: #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia [-Wcpp]
   51 |   #warning theyre out here saying ca daca le tii in map direct e O(N) toata chestia
      |    ^~~~~~~
segments.cpp:52:4: warning: #warning poate e doar Bmax sau ceva (700) (pt MLE sau cv) [-Wcpp]
   52 |   #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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 5 ms 8540 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 10 ms 9844 KB Output is correct
6 Correct 12 ms 9564 KB Output is correct
7 Correct 7 ms 8796 KB Output is correct
8 Correct 8 ms 9308 KB Output is correct
9 Correct 8 ms 9308 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 25 ms 9728 KB Output is correct
12 Correct 20 ms 9504 KB Output is correct
13 Correct 7 ms 9820 KB Output is correct
14 Correct 9 ms 9380 KB Output is correct
15 Correct 5 ms 8540 KB Output is correct
16 Correct 5 ms 8784 KB Output is correct
17 Correct 9 ms 9052 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 7 ms 9052 KB Output is correct
20 Correct 8 ms 9048 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8992 KB Output is correct
2 Correct 68 ms 9040 KB Output is correct
3 Correct 76 ms 9044 KB Output is correct
4 Correct 84 ms 8912 KB Output is correct
5 Correct 399 ms 27844 KB Output is correct
6 Correct 613 ms 25400 KB Output is correct
7 Correct 501 ms 26568 KB Output is correct
8 Correct 198 ms 33276 KB Output is correct
9 Correct 677 ms 31964 KB Output is correct
10 Correct 1155 ms 25988 KB Output is correct
11 Correct 138 ms 9852 KB Output is correct
12 Correct 1055 ms 26284 KB Output is correct
13 Correct 861 ms 24288 KB Output is correct
14 Correct 672 ms 16656 KB Output is correct
15 Correct 578 ms 15440 KB Output is correct
16 Correct 399 ms 13312 KB Output is correct
17 Correct 1087 ms 22928 KB Output is correct
18 Correct 1039 ms 22788 KB Output is correct
19 Correct 1000 ms 23184 KB Output is correct
20 Correct 1020 ms 22996 KB Output is correct
21 Correct 170 ms 10572 KB Output is correct
22 Correct 765 ms 18324 KB Output is correct
23 Correct 887 ms 21968 KB Output is correct
24 Correct 833 ms 19044 KB Output is correct
25 Correct 73 ms 9040 KB Output is correct
26 Correct 69 ms 9048 KB Output is correct
27 Correct 91 ms 9156 KB Output is correct
28 Correct 70 ms 9092 KB Output is correct
29 Correct 987 ms 22968 KB Output is correct
30 Correct 1034 ms 22760 KB Output is correct
31 Correct 590 ms 32604 KB Output is correct
32 Correct 1116 ms 25880 KB Output is correct
33 Correct 1066 ms 24432 KB Output is correct
34 Correct 488 ms 15040 KB Output is correct
35 Correct 941 ms 21804 KB Output is correct
36 Correct 922 ms 25284 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8900 KB Output is correct
2 Correct 84 ms 9040 KB Output is correct
3 Correct 82 ms 9092 KB Output is correct
4 Correct 90 ms 9044 KB Output is correct
5 Correct 2814 ms 30440 KB Output is correct
6 Execution timed out 5037 ms 20732 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 5 ms 8540 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 10 ms 9844 KB Output is correct
6 Correct 12 ms 9564 KB Output is correct
7 Correct 7 ms 8796 KB Output is correct
8 Correct 8 ms 9308 KB Output is correct
9 Correct 8 ms 9308 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 25 ms 9728 KB Output is correct
12 Correct 20 ms 9504 KB Output is correct
13 Correct 7 ms 9820 KB Output is correct
14 Correct 9 ms 9380 KB Output is correct
15 Correct 5 ms 8540 KB Output is correct
16 Correct 5 ms 8784 KB Output is correct
17 Correct 9 ms 9052 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 7 ms 9052 KB Output is correct
20 Correct 8 ms 9048 KB Output is correct
21 Execution timed out 5025 ms 24820 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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 5 ms 8540 KB Output is correct
4 Correct 5 ms 8540 KB Output is correct
5 Correct 10 ms 9844 KB Output is correct
6 Correct 12 ms 9564 KB Output is correct
7 Correct 7 ms 8796 KB Output is correct
8 Correct 8 ms 9308 KB Output is correct
9 Correct 8 ms 9308 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 25 ms 9728 KB Output is correct
12 Correct 20 ms 9504 KB Output is correct
13 Correct 7 ms 9820 KB Output is correct
14 Correct 9 ms 9380 KB Output is correct
15 Correct 5 ms 8540 KB Output is correct
16 Correct 5 ms 8784 KB Output is correct
17 Correct 9 ms 9052 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 7 ms 9052 KB Output is correct
20 Correct 8 ms 9048 KB Output is correct
21 Execution timed out 5025 ms 24820 KB Time limit exceeded
22 Halted 0 ms 0 KB -