oj.uz

Submission #1046754

# Submission time Handle Problem Language Result Execution time Memory
1046754 2024-08-06T21:32:57 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 93624 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) return;
    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:200:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  200 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:222:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  222 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:232:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  232 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:245:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  245 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:333: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]
  333 |       while(p < R.size() && R[p][0] == l){
      |             ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:360:17: warning: unused variable 'aa' [-Wunused-variable]
  360 |     int tt = 1, aa;
      |                 ^~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 44192 KB Output is correct
2 Correct 1172 ms 43120 KB Output is correct
3 Correct 1714 ms 44448 KB Output is correct
4 Correct 3072 ms 70584 KB Output is correct
5 Correct 1820 ms 54712 KB Output is correct
6 Correct 3491 ms 74476 KB Output is correct
7 Correct 1792 ms 72788 KB Output is correct
8 Correct 66 ms 36728 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11100 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 3 ms 10960 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Execution timed out 5097 ms 93624 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 6 ms 11100 KB Output is correct
5 Correct 950 ms 47552 KB Output is correct
6 Correct 2086 ms 58528 KB Output is correct
7 Correct 3527 ms 74368 KB Output is correct
8 Execution timed out 5063 ms 88180 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10712 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 910 ms 44192 KB Output is correct
9 Correct 1172 ms 43120 KB Output is correct
10 Correct 1714 ms 44448 KB Output is correct
11 Correct 3072 ms 70584 KB Output is correct
12 Correct 1820 ms 54712 KB Output is correct
13 Correct 3491 ms 74476 KB Output is correct
14 Correct 1792 ms 72788 KB Output is correct
15 Correct 66 ms 36728 KB Output is correct
16 Correct 5 ms 11100 KB Output is correct
17 Correct 4 ms 10844 KB Output is correct
18 Correct 3 ms 10960 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Execution timed out 5097 ms 93624 KB Time limit exceeded
21 Halted 0 ms 0 KB -