oj.uz

Submission #1046747

# Submission time Handle Problem Language Result Execution time Memory
1046747 2024-08-06T21:31:07 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
20 / 100
 2554 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int NN = 2e6+100, M = 3e5+10, K = 52, MX = 30;
    

#define upd_sz(_v) {if(_v){_v->sum = _v->val * _v->key;_v->sum2 = _v->val;if(_v->left) _v->sum += _v->left->sum;if(_v->right) _v->sum += _v->right->sum;if(_v->left) _v->sum2 += _v->left->sum2;if(_v->right) _v->sum2 += _v->right->sum2;}}
    
// An AVL tree node 
class Node 
{ 
  public: 
  int key; 
  Node *left; 
  Node *right; 
  int height, sum, sum2, val; 
}; 

// A utility function to get the 
// height of the tree 
int height(Node *N) 
{ 
  if (N == NULL) 
    return 0; 
  return N->height; 
} 


/* Helper function that allocates a 
new node with the given key and 
NULL left and right pointers. */
Node* newNode(int key, int val) 
{ 
  Node* node = new Node(); 
  node->key = key; 
  node->left = NULL; 
  node->right = NULL; 
  node->height = 1; // new node is initially 
  node->val = val;
  node->sum = key * val;
  node->sum2 = val;
          // added at leaf 
  return(node); 
} 

// A utility function to right 
// rotate subtree rooted with y 
// See the diagram given above. 
Node *rightRotate(Node *y) 
{ 
  Node *x = y->left; 
  Node *T2 = x->right; 

  // Perform rotation 
  x->right = y; 
  y->left = T2; 

  // Update heights 
  y->height = max(height(y->left), 
          height(y->right)) + 1; 
  x->height = max(height(x->left), 
          height(x->right)) + 1; 
  upd_sz(x);
  upd_sz(y);
  upd_sz(x);
  upd_sz(y);
  // Return new root 
  return x; 
} 

// A utility function to left 
// rotate subtree rooted with x 
// See the diagram given above. 
Node *leftRotate(Node *x) 
{ 
  Node *y = x->right; 
  Node *T2 = y->left; 

  // Perform rotation 
  y->left = x; 
  x->right = T2; 

  // Update heights 
  x->height = max(height(x->left),   
          height(x->right)) + 1; 
  y->height = max(height(y->left), 
          height(y->right)) + 1; 

  upd_sz(y);
  upd_sz(x);
  upd_sz(y);
  upd_sz(x);
  // Return new root 
  return y; 
} 

// Get Balance factor of node N 
int getBalance(Node *N) 
{ 
  if (N == NULL) 
    return 0; 
  return height(N->left) - height(N->right); 
} 

// Recursive function to insert a key 
// in the subtree rooted with node and 
// returns the new root of the subtree. 
Node* insert(Node* node, int key, int val) 
{ 
  /* 1. Perform the normal BST insertion */
  if (node == NULL) 
    return(newNode(key, val)); 

  if (key < node->key) 
    node->left = insert(node->left, key, val); 
  else if (key >= node->key) 
    node->right = insert(node->right, key, val); 

  /* 2. Update height of this ancestor node */
  node->height = 1 + max(height(node->left), 
            height(node->right)); 

  /* 3. Get the balance factor of this ancestor 
    node to check whether this node became 
    unbalanced */
  int balance = getBalance(node); 

  // If this node becomes unbalanced, then 
  // there are 4 cases 

  // Left Left Case 
  if (balance > 1 && key < node->left->key) 
    return rightRotate(node); 

  // Right Right Case 
  if (balance < -1 && key >= node->right->key) 
    return leftRotate(node); 

  // Left Right Case 
  if (balance > 1 && key >= node->left->key) 
  { 
    node->left = leftRotate(node->left); 
    return rightRotate(node); 
  } 

  // Right Left Case 
  if (balance < -1 && key < node->right->key) 
  { 
    node->right = rightRotate(node->right); 
    return leftRotate(node); 
  } 

  upd_sz(node);

  /* return the (unchanged) node pointer */
  return node; 
} 

typedef Node* Nodep; 
     
int query(Nodep p, int key){
  int val = 0;
  while(p){
    if(p->key <= key){
      val += p->val * key - p->val * p->key;
      if(p->left) val += p->left->sum2 * key - p->left->sum;
      p = p->right;
    }else{
      p = p->left;
    }  
  }
  return val;
}
    
inline void dfs(Nodep t){
    // if(t->left) dfs(t->left);
    // if(t->right) dfs(t->right);
    // free(t);
}

    
    
int n, q, ans[M];
string s;
Nodep T[NN];
    
inline void build(int l, int r, int k){
    if(l == r){
    T[k] = NULL;
    return;
    }
    int m = l+r>>1;
    build(l, m, k<<1);
    build(m+1, r, k<<1|1);
    T[k] = NULL;
}
    
inline void upd(int l, int r, int p, int k, int t1, int t2){
    if(!(l == 1 && r == n)){
        // Nodep A = new Node(t1, 1);
        // Nodep B = new Node(t2, -1);
      // cout << l << ' ' << r << ' ' << t1 << ' ' << t2 << endl;
        T[k] = insert(T[k], t1, 1);
        // cout << "wtf" << endl;
        T[k] = insert(T[k], t2, -1);
        // cout << l << ' ' << r << ' ' << t1 << ' ' << t2 << endl;
    }
    // dfs2(T[k]);en;en;
    // cout << "insert:" << l << ' ' << r << ' ' << p << ' ' << t1 << ' ' << t2 << '\n';
    
    if(l == r){
    return;
    }
    int m = l+r>>1;
    if(p <= m) upd(l, m, p, k<<1, t1, t2);
    else upd(m+1, r, p, k<<1|1, t1, t2);
}
    
inline int get(int l, int r, int p, int k, int tm){
    if(l == r){
      return query(T[k],tm); 
    }
    // dfs2(T[k]);en;en;
    int m = l+r>>1;
    if(p <= m){
        int val = query(T[k<<1|1],tm);
        return get(l, m, p, k<<1, tm) + val;
    }
    return get(m+1, r, p, k<<1|1, tm);
}
    
inline void F(int l, int r, int p, int k){
    if(l == r){
    dfs(T[k]);
    return;
    }
    int m = l+r>>1;
    if(p <= m) F(l, m, p, k<<1);
    else F(m+1, r, p, k<<1|1);
    if(p == r) dfs(T[k]);
}
    
vector<array<int, 3>> Q[M];
inline void solve(){
    // cout << sizeof(Node) << '\n';
    cin >> n >> q >> s;
    
    vector<int> val;
    vector<array<int, 4>> R, QQ; 
    int last = 1;
    s += '0';
    set<array<int, 3>> S;
    for(int i = 0; i <= n; ++i){
    if(s[i] == '0'){
        S.insert({last, i + 1, 0});
        last = i + 2;
    }
    }
    
    int qq = 0;
    
    for(int i = 0; i < q; ++i){
    string x; int a, b; cin >> x;
    if(x == "toggle"){
        cin >> a;
        --a;
        if(s[a] == '0'){
        s[a] = '1';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        auto it2 = prev(it);
        auto x = *it, y = *it2;
        S.erase(it2);
        S.erase(S.find(x));
        S.insert({y[0], x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
        R.pb({y[0], y[1], y[2], i + 1});
        }else{
        s[a] = '0';
        ++a;
        auto it = S.lower_bound(array<int, 3>{a + 1, -1, -1});
        assert(it != S.begin());
        it = prev(it);
        auto x = *it;
        S.erase(it);
        S.insert({x[0], a, i + 1}); // check
        S.insert({a + 1, x[1], i + 1}); // check
        R.pb({x[0], x[1], x[2], i + 1});
        }
    }else{
        cin >> a >> b;
        QQ.pb({a, b, i + 1, qq});
        qq++;
    }
    }
    
    for(auto p: S){
      R.pb({p[0], p[1], p[2], q});
    }
    for(auto p: R) val.pb(p[1]);
    sort(all(val));
    val.erase(unique(all(val)), val.end());
    for(auto &p: R){
      p[0] = lower_bound(all(val), p[0]) - val.begin() + 1;
      p[1] = lower_bound(all(val), p[1]) - val.begin() + 1;
    }
    for(auto &p :QQ){
      p[0] = lower_bound(all(val), p[0]) - val.begin() + 1;
      p[1] = lower_bound(all(val), p[1]) - val.begin() + 1;
      Q[p[0]].pb({p[1], p[2], p[3]});
    }
    S.clear();
    
    sort(all(R));
    n = val.size() + 1;
    build(1, n, 1);
    int p = 0;
    // for(auto f: R){
    //   cout << f[0] << ' ' << f[1] << ' ' << f[2] << ' ' << f[3] << '\n';
    // }
    // en;en;
    
    for(int l = 1; l <= n; ++l){
      while(p < R.size() && R[p][0] == l){
              // cout << R[p][0] << ' ' << R[p][1] << ' ' << R[p][2] << ' ' << R[p][3] << endl;
        // cout << endl;
          int r = R[p][1], t1 = R[p][2], t2 = R[p][3];
          upd(1, n, r, 1, t1, t2);
          ++p;
      }
      for(auto query: Q[l]){
          int r = query[0], tm = query[1], idx = query[2];
              // cout << l << ' ' << r << endl;
      
          ans[idx] = get(1, n, r, 1, tm);
          //  cout << ans[idx] << ' ';
          // en;en;
      }
      // if(l <= n/2)
      F(1, n, l, 1);
    }
    
    
    
    for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
}
    
    
int32_t main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int tt = 1, aa;
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    while(tt--){
    solve();
    }
    cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
    return 0;
}

Compilation message

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:199:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  199 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:221:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  221 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:231:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  231 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:244:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  244 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:332:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  332 |       while(p < R.size() && R[p][0] == l){
      |             ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:359:17: warning: unused variable 'aa' [-Wunused-variable]
  359 |     int tt = 1, aa;
      |                 ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 165328 KB Output is correct
2 Correct 886 ms 201164 KB Output is correct
3 Correct 1341 ms 291480 KB Output is correct
4 Runtime error 1908 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12632 KB Output is correct
2 Correct 4 ms 12016 KB Output is correct
3 Correct 4 ms 11612 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Runtime error 2554 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 4 ms 11612 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 6 ms 12528 KB Output is correct
5 Correct 752 ms 288632 KB Output is correct
6 Correct 1631 ms 508240 KB Output is correct
7 Runtime error 1923 ms 524288 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 685 ms 165328 KB Output is correct
9 Correct 886 ms 201164 KB Output is correct
10 Correct 1341 ms 291480 KB Output is correct
11 Runtime error 1908 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -