oj.uz

답안 #1046696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1046696 2024-08-06T20:43:28 Z mychecksedad 가로등 (APIO19_street_lamps) C++17
40 / 100
 5000 ms 472592 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 1 ms 11004 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 875 ms 113452 KB Output is correct
2 Correct 1162 ms 130468 KB Output is correct
3 Correct 1843 ms 176312 KB Output is correct
4 Correct 3083 ms 407836 KB Output is correct
5 Correct 2043 ms 276480 KB Output is correct
6 Correct 3540 ms 448380 KB Output is correct
7 Correct 1670 ms 339608 KB Output is correct
8 Correct 133 ms 63204 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 5 ms 11612 KB Output is correct
4 Correct 7 ms 11868 KB Output is correct
5 Correct 898 ms 198576 KB Output is correct
6 Correct 2147 ms 321224 KB Output is correct
7 Correct 3639 ms 448648 KB Output is correct
8 Execution timed out 5059 ms 472592 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 1 ms 11004 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 1 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 875 ms 113452 KB Output is correct
9 Correct 1162 ms 130468 KB Output is correct
10 Correct 1843 ms 176312 KB Output is correct
11 Correct 3083 ms 407836 KB Output is correct
12 Correct 2043 ms 276480 KB Output is correct
13 Correct 3540 ms 448380 KB Output is correct
14 Correct 1670 ms 339608 KB Output is correct
15 Correct 133 ms 63204 KB Output is correct
16 Correct 6 ms 11904 KB Output is correct
17 Correct 5 ms 11612 KB Output is correct
18 Correct 4 ms 11356 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Execution timed out 5113 ms 442176 KB Time limit exceeded
21 Halted 0 ms 0 KB -