oj.uz

Submission #1045347

# Submission time Handle Problem Language Result Execution time Memory
1045347 2024-08-05T20:55:37 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 135004 KB 
/* Author : Mychecksdead  */
#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
#define int int_fast32_t
const int N = 2e6+100, M = 3e5+10, K = 52, MX = 30;
    
struct Node{
    int X, sum = 0, sum2 = 0;
    int Y, val;
    Node *L, *R;
    Node(){}
    Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
};
typedef Node* Nodep; 
    
#define upd_sz(_v) {if(_v){_v->sum = _v->val * _v->X;_v->sum2 = _v->val;if(_v->L) _v->sum += _v->L->sum;if(_v->R) _v->sum += _v->R->sum;if(_v->L) _v->sum2 += _v->L->sum2;if(_v->R) _v->sum2 += _v->R->sum2;}}
    
inline pair<Nodep, Nodep> split(Nodep v, int key){
    if(!v){
        return {v, v};
    }
    else if(v->X <= key){
        auto p = split(v->R, key);
        v->R = p.first;
        upd_sz(v);
        return {v, p.second};
    }else{
        auto p = split(v->L, key);
        v->L = p.second;
        upd_sz(v);
        return {p.first, v};
    }
}
    

int query(Nodep p, int key){
  int val = 0;
  while(p){
    if(p->X <= key){
      val += p->val * key - p->val * p->X;
      if(p->L) val += p->L->sum2 * key - p->L->sum;
      p = p->R;
    }else{
      p = p->L;
    }  
  }
  return val;
}
 
inline Nodep insert(Nodep v, Nodep it){
    if(!v) return it;
    if(v->Y > it->Y){
    if(v->X <= it->X) v->R = insert(v->R, it);
    else v->L = insert(v->L, it);
    upd_sz(v);
    return v;
    }else{
    auto a = split(v, it->X);
    it->L = a.ff;
    it->R = a.ss;
    upd_sz(it);
    }
    return it;
}
    
inline void dfs(Nodep t){
    if(t->L) dfs(t->L);
    if(t->R) dfs(t->R);
    free(t);
}
    
inline void dfs2(Nodep t){
    // if(t->L)
    // cout << "go left: ";
    if(t->L) dfs2(t->L);
    // cout << "par: ";
    // cout << t->Y << ' ';
    // if(t->R)
    // cout << "go right: ";
    if(t->R) dfs2(t->R);
}
    
    
int n, q, ans[M];
string s;
Nodep T[N];
    
inline void build(int l, int r, int k){
    if(l == r){
    T[k] = new Node(0, 0);
    return;
    }
    int m = l+r>>1;
    build(l, m, k<<1);
    build(m+1, r, k<<1|1);
    T[k] = new Node(0, 0);
}
    
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);
        T[k] = insert(T[k], A);
        T[k] = insert(T[k], B);
    }
    // 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<array<int, 4>> R;
    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;
        Q[a].pb({b, i + 1, qq});
        qq++;
    }
    }
    
    for(auto p: S){
    R.pb({p[0], p[1], p[2], q});
    }
    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 + 1; ++l){
    while(p < R.size() && R[p][0] == l){
            // cout << R[p][0] << ' ' << R[p][1] << ' ' << R[p][2] << ' ' << R[p][3] << '\n';
    
        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 << '\n';
    
        ans[idx] = get(1, n + 1, r, 1, tm);
        //  cout << ans[idx] << ' ';
        // en;en;
    }
    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 constructor 'Node::Node(int_fast32_t, int_fast32_t)':
street_lamps.cpp:18:15: warning: 'Node::R' will be initialized after [-Wreorder]
   18 |     Node *L, *R;
      |               ^
street_lamps.cpp:17:12: warning:   'int_fast32_t Node::val' [-Wreorder]
   17 |     int Y, val;
      |            ^~~
street_lamps.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |     ^~~~
street_lamps.cpp:17:12: warning: 'Node::val' will be initialized after [-Wreorder]
   17 |     int Y, val;
      |            ^~~
street_lamps.cpp:16:12: warning:   'int_fast32_t Node::sum' [-Wreorder]
   16 |     int X, sum = 0, sum2 = 0;
      |            ^~~
street_lamps.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     Node(int key, int val) : X(key), Y(rand()), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |     ^~~~
street_lamps.cpp: In function 'void build(int_fast32_t, int_fast32_t, int_fast32_t)':
street_lamps.cpp:101:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void upd(int_fast32_t, int_fast32_t, int_fast32_t, int_fast32_t, int_fast32_t, int_fast32_t)':
street_lamps.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'int_fast32_t get(int_fast32_t, int_fast32_t, int_fast32_t, int_fast32_t, int_fast32_t)':
street_lamps.cpp:130:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void F(int_fast32_t, int_fast32_t, int_fast32_t, int_fast32_t)':
street_lamps.cpp:143:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:218:13: warning: comparison of integer expressions of different signedness: 'int_fast32_t' {aka 'long int'} and 'std::vector<std::array<long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:244:17: warning: unused variable 'aa' [-Wunused-variable]
  244 |     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 2 ms 10844 KB Output is correct
3 Correct 1 ms 10832 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10840 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 55592 KB Output is correct
2 Correct 1327 ms 54316 KB Output is correct
3 Correct 1986 ms 54960 KB Output is correct
4 Correct 3500 ms 104640 KB Output is correct
5 Correct 2278 ms 86644 KB Output is correct
6 Correct 4257 ms 110360 KB Output is correct
7 Correct 1899 ms 98848 KB Output is correct
8 Correct 154 ms 70888 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11096 KB Output is correct
2 Correct 5 ms 11100 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Execution timed out 5070 ms 133936 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 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 6 ms 11100 KB Output is correct
5 Correct 1038 ms 80484 KB Output is correct
6 Correct 2378 ms 93640 KB Output is correct
7 Correct 4205 ms 110284 KB Output is correct
8 Execution timed out 5058 ms 135004 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 2 ms 10844 KB Output is correct
3 Correct 1 ms 10832 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 1 ms 10840 KB Output is correct
8 Correct 1054 ms 55592 KB Output is correct
9 Correct 1327 ms 54316 KB Output is correct
10 Correct 1986 ms 54960 KB Output is correct
11 Correct 3500 ms 104640 KB Output is correct
12 Correct 2278 ms 86644 KB Output is correct
13 Correct 4257 ms 110360 KB Output is correct
14 Correct 1899 ms 98848 KB Output is correct
15 Correct 154 ms 70888 KB Output is correct
16 Correct 6 ms 11096 KB Output is correct
17 Correct 5 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Execution timed out 5070 ms 133936 KB Time limit exceeded
21 Halted 0 ms 0 KB -