oj.uz

Submission #1046704

# Submission time Handle Problem Language Result Execution time Memory
1046704 2024-08-06T20:46:38 Z mychecksedad Street Lamps (APIO19_street_lamps) C++17
20 / 100
 2532 ms 524288 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
const int N = 2e6+100, M = 3e5+10, K = 52, MX = 30;
    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ree(int l, int r){
  return uniform_int_distribution<int>(l, r)(rng);
}

struct Node{
    int X, sum = 0, sum2 = 0;
    int Y, val;
    Node *L, *R;
    Node(){}
    Node(int key, int val) : X(key), Y(ree(-INT_MAX, INT_MAX)), 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;
    }
    // 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 constructor 'Node::Node(int, int)':
street_lamps.cpp:22:15: warning: 'Node::R' will be initialized after [-Wreorder]
   22 |     Node *L, *R;
      |               ^
street_lamps.cpp:21:12: warning:   'int Node::val' [-Wreorder]
   21 |     int Y, val;
      |            ^~~
street_lamps.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Node(int key, int val) : X(key), Y(ree(-INT_MAX, INT_MAX)), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |     ^~~~
street_lamps.cpp:21:12: warning: 'Node::val' will be initialized after [-Wreorder]
   21 |     int Y, val;
      |            ^~~
street_lamps.cpp:20:12: warning:   'int Node::sum' [-Wreorder]
   20 |     int X, sum = 0, sum2 = 0;
      |            ^~~
street_lamps.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Node(int key, int val) : X(key), Y(ree(-INT_MAX, INT_MAX)), L(nullptr), R(nullptr), val(val), sum(key * val), sum2(val) {}
      |     ^~~~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:105:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:124:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:134:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:147:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:222:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:249:17: warning: unused variable 'aa' [-Wunused-variable]
  249 |     int tt = 1, aa;
      |                 ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 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 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 160300 KB Output is correct
2 Correct 1031 ms 193720 KB Output is correct
3 Correct 1678 ms 283244 KB Output is correct
4 Runtime error 2052 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 6 ms 12892 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 3 ms 11612 KB Output is correct
4 Correct 2 ms 10848 KB Output is correct
5 Runtime error 2532 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 11696 KB Output is correct
3 Correct 4 ms 12252 KB Output is correct
4 Correct 6 ms 12824 KB Output is correct
5 Correct 835 ms 323336 KB Output is correct
6 Runtime error 1843 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 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 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 773 ms 160300 KB Output is correct
9 Correct 1031 ms 193720 KB Output is correct
10 Correct 1678 ms 283244 KB Output is correct
11 Runtime error 2052 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -