oj.uz

답안 #1045320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045320 2024-08-05T20:24:41 Z noyancanturk 가로등 (APIO19_street_lamps) C++17
40 / 100
 5000 ms 98764 KB 
/* Author : Mychecksdead  */
#pragma GCC optimize("O3,unroll-loops")
#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;
    
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};
    }
}
    
inline int query(Nodep p,int key){
    if(!p)return 0;
    if(p->X<=key){
        int toret=p->val*key-p->val*p->X;
        if(p->L)toret+=p->L->sum2*key-p->L->sum;
        return toret+query(p->R,key);
    }
    return query(p->L,key);
}

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, ll 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';
}
    
    
int 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:18:15: warning: 'Node::R' will be initialized after [-Wreorder]
   18 |     Node *L, *R;
      |               ^
street_lamps.cpp:17:12: warning:   'int 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 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, int, int)':
street_lamps.cpp:96:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void upd(int, int, int, int, int, int)':
street_lamps.cpp:115:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'int get(int, int, int, int, long long int)':
street_lamps.cpp:125:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void F(int, int, int, int)':
street_lamps.cpp:138:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     int m = l+r>>1;
      |             ~^~
street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:213: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]
  213 |     while(p < R.size() && R[p][0] == l){
      |           ~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:239:17: warning: unused variable 'aa' [-Wunused-variable]
  239 |     int tt = 1, aa;
      |                 ^~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 983 ms 38840 KB Output is correct
2 Correct 1253 ms 38100 KB Output is correct
3 Correct 1855 ms 38116 KB Output is correct
4 Correct 3688 ms 77740 KB Output is correct
5 Correct 2211 ms 65748 KB Output is correct
6 Correct 3873 ms 82892 KB Output is correct
7 Correct 1870 ms 73676 KB Output is correct
8 Correct 148 ms 55268 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9048 KB Output is correct
2 Correct 5 ms 8796 KB Output is correct
3 Correct 4 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Execution timed out 5082 ms 98764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 5 ms 9032 KB Output is correct
4 Correct 6 ms 9080 KB Output is correct
5 Correct 997 ms 60728 KB Output is correct
6 Correct 2326 ms 70608 KB Output is correct
7 Correct 3952 ms 82120 KB Output is correct
8 Execution timed out 5017 ms 98360 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 983 ms 38840 KB Output is correct
9 Correct 1253 ms 38100 KB Output is correct
10 Correct 1855 ms 38116 KB Output is correct
11 Correct 3688 ms 77740 KB Output is correct
12 Correct 2211 ms 65748 KB Output is correct
13 Correct 3873 ms 82892 KB Output is correct
14 Correct 1870 ms 73676 KB Output is correct
15 Correct 148 ms 55268 KB Output is correct
16 Correct 7 ms 9048 KB Output is correct
17 Correct 5 ms 8796 KB Output is correct
18 Correct 4 ms 8792 KB Output is correct
19 Correct 3 ms 8792 KB Output is correct
20 Execution timed out 5082 ms 98764 KB Time limit exceeded
21 Halted 0 ms 0 KB -