oj.uz

답안 #1046868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046868 2024-08-07T05:24:31 Z mychecksedad 가로등 (APIO19_street_lamps) C++17
40 / 100
 5000 ms 90676 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10840 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 1 ms 10836 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 817 ms 44412 KB Output is correct
2 Correct 1020 ms 44244 KB Output is correct
3 Correct 1520 ms 44952 KB Output is correct
4 Correct 2967 ms 66748 KB Output is correct
5 Correct 1908 ms 49704 KB Output is correct
6 Correct 3666 ms 69096 KB Output is correct
7 Correct 1625 ms 66724 KB Output is correct
8 Correct 60 ms 31436 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 11100 KB Output is correct
2 Correct 6 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Execution timed out 5100 ms 90676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 823 ms 46452 KB Output is correct
6 Correct 1987 ms 58556 KB Output is correct
7 Correct 3228 ms 69836 KB Output is correct
8 Execution timed out 5059 ms 84676 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10840 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 1 ms 10836 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 817 ms 44412 KB Output is correct
9 Correct 1020 ms 44244 KB Output is correct
10 Correct 1520 ms 44952 KB Output is correct
11 Correct 2967 ms 66748 KB Output is correct
12 Correct 1908 ms 49704 KB Output is correct
13 Correct 3666 ms 69096 KB Output is correct
14 Correct 1625 ms 66724 KB Output is correct
15 Correct 60 ms 31436 KB Output is correct
16 Correct 5 ms 11100 KB Output is correct
17 Correct 6 ms 10844 KB Output is correct
18 Correct 3 ms 10844 KB Output is correct
19 Correct 1 ms 10844 KB Output is correct
20 Execution timed out 5100 ms 90676 KB Time limit exceeded
21 Halted 0 ms 0 KB -