oj.uz

Submission #927757

# Submission time Handle Problem Language Result Execution time Memory
927757 2024-02-15T09:58:41 Z cadmiumsky Segments (IZhO18_segments) C++17
7 / 100
 5000 ms 26372 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 || 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: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)
      |    ^~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:197:12: warning: unused variable 'worstInner' [-Wunused-variable]
  197 |   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 8 ms 8540 KB Output is correct
4 Correct 7 ms 8540 KB Output is correct
5 Correct 404 ms 9644 KB Output is correct
6 Correct 518 ms 9564 KB Output is correct
7 Correct 222 ms 8832 KB Output is correct
8 Correct 560 ms 9332 KB Output is correct
9 Correct 600 ms 9288 KB Output is correct
10 Correct 263 ms 9564 KB Output is correct
11 Correct 659 ms 9252 KB Output is correct
12 Correct 665 ms 9504 KB Output is correct
13 Correct 274 ms 9560 KB Output is correct
14 Correct 540 ms 9228 KB Output is correct
15 Correct 7 ms 8540 KB Output is correct
16 Correct 20 ms 8716 KB Output is correct
17 Correct 419 ms 9044 KB Output is correct
18 Correct 383 ms 9564 KB Output is correct
19 Correct 441 ms 9264 KB Output is correct
20 Correct 464 ms 9028 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 9112 KB Output is correct
2 Correct 319 ms 8988 KB Output is correct
3 Correct 2932 ms 9216 KB Output is correct
4 Correct 436 ms 9024 KB Output is correct
5 Execution timed out 5082 ms 25064 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 8788 KB Output is correct
2 Correct 417 ms 9000 KB Output is correct
3 Correct 391 ms 9476 KB Output is correct
4 Correct 700 ms 9040 KB Output is correct
5 Execution timed out 5069 ms 26372 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 8 ms 8540 KB Output is correct
4 Correct 7 ms 8540 KB Output is correct
5 Correct 404 ms 9644 KB Output is correct
6 Correct 518 ms 9564 KB Output is correct
7 Correct 222 ms 8832 KB Output is correct
8 Correct 560 ms 9332 KB Output is correct
9 Correct 600 ms 9288 KB Output is correct
10 Correct 263 ms 9564 KB Output is correct
11 Correct 659 ms 9252 KB Output is correct
12 Correct 665 ms 9504 KB Output is correct
13 Correct 274 ms 9560 KB Output is correct
14 Correct 540 ms 9228 KB Output is correct
15 Correct 7 ms 8540 KB Output is correct
16 Correct 20 ms 8716 KB Output is correct
17 Correct 419 ms 9044 KB Output is correct
18 Correct 383 ms 9564 KB Output is correct
19 Correct 441 ms 9264 KB Output is correct
20 Correct 464 ms 9028 KB Output is correct
21 Execution timed out 5041 ms 20356 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 8 ms 8540 KB Output is correct
4 Correct 7 ms 8540 KB Output is correct
5 Correct 404 ms 9644 KB Output is correct
6 Correct 518 ms 9564 KB Output is correct
7 Correct 222 ms 8832 KB Output is correct
8 Correct 560 ms 9332 KB Output is correct
9 Correct 600 ms 9288 KB Output is correct
10 Correct 263 ms 9564 KB Output is correct
11 Correct 659 ms 9252 KB Output is correct
12 Correct 665 ms 9504 KB Output is correct
13 Correct 274 ms 9560 KB Output is correct
14 Correct 540 ms 9228 KB Output is correct
15 Correct 7 ms 8540 KB Output is correct
16 Correct 20 ms 8716 KB Output is correct
17 Correct 419 ms 9044 KB Output is correct
18 Correct 383 ms 9564 KB Output is correct
19 Correct 441 ms 9264 KB Output is correct
20 Correct 464 ms 9028 KB Output is correct
21 Execution timed out 5041 ms 20356 KB Time limit exceeded
22 Halted 0 ms 0 KB -