oj.uz

Submission #1046871

# Submission time Handle Problem Language Result Execution time Memory
1046871 2024-08-07T05:26:24 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 85688 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 + 1)){
        // 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 :QQ){
      Q[p[0]].pb({p[1], p[2], p[3]});
    }
    S.clear();
    
    sort(all(R));
    build(1, n + 1, 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 + 1, 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 + 1, r, 1, tm);
          //  cout << ans[idx] << ' ';
          // en;en;
      }
      // if(l <= n/2)
      F(1, n + 1, 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:323: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]
  323 |       while(p < R.size() && R[p][0] == l){
      |             ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:350:17: warning: unused variable 'aa' [-Wunused-variable]
  350 |     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 2 ms 10844 KB Output is correct
6 Correct 2 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 831 ms 43232 KB Output is correct
2 Correct 1054 ms 42524 KB Output is correct
3 Correct 1621 ms 43484 KB Output is correct
4 Correct 2698 ms 68280 KB Output is correct
5 Correct 1674 ms 55232 KB Output is correct
6 Correct 3205 ms 72692 KB Output is correct
7 Correct 1513 ms 67848 KB Output is correct
8 Correct 99 ms 34508 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 4 ms 11096 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 791 ms 50632 KB Output is correct
6 Correct 1918 ms 62028 KB Output is correct
7 Correct 3254 ms 70924 KB Output is correct
8 Execution timed out 5044 ms 85444 KB Time limit exceeded
9 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 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 831 ms 43232 KB Output is correct
9 Correct 1054 ms 42524 KB Output is correct
10 Correct 1621 ms 43484 KB Output is correct
11 Correct 2698 ms 68280 KB Output is correct
12 Correct 1674 ms 55232 KB Output is correct
13 Correct 3205 ms 72692 KB Output is correct
14 Correct 1513 ms 67848 KB Output is correct
15 Correct 99 ms 34508 KB Output is correct
16 Correct 5 ms 11096 KB Output is correct
17 Correct 4 ms 10844 KB Output is correct
18 Correct 3 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Execution timed out 5097 ms 85688 KB Time limit exceeded
21 Halted 0 ms 0 KB -