oj.uz

답안 #405557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405557 2021-05-16T14:25:55 Z Jarif_Rahman 가로등 (APIO19_street_lamps) C++17
20 / 100
 943 ms 74336 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void upd(int in, int x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};
struct segtree{
    int k, n;
    vector<int> mn;
    segtree(int _n){
        n = _n;
        k = 1;
        while(k < n) k*=2;
        k*=2;
        mn.resize(k, 1);
    }
    void toggle(int in){
        in+=k/2;
        mn[in] = !mn[in];
        in/=2;
        while(in > 0){
            mn[in] = min(mn[2*in], mn[2*in+1]);
            in/=2;
        }
    }
    int get(int in){
        return mn[in+k/2];
    }
    int find(int in, int nd, int a, int b){
        if(mn[nd] == 1) return -1;
        if(in > b) return -1;
        if(a == b) return a;
        int md = (a+b)/2;
        int x;
        return (x = find(in, 2*nd, a, md)) == -1 ?  find(in, 2*nd+1, md+1, b) : x;
    }
    int find(int in){
        int x = find(in, 1, 0, k/2-1);
        if(x == -1) x = n;
        x--;
        return x;
    }
    int rfind(int in, int nd, int a, int b){
        if(mn[nd] == 1) return -1;
        if(in < a) return -1;
        if(a == b) return a;
        int md = (a+b)/2;
        int x;
        return (x = rfind(in, 2*nd+1, md+1, b)) == -1 ?  rfind(in, 2*nd, a, md) : x;
    }
    int rfind(int in){
        int x = rfind(in, 1, 0, k/2-1);
        x++;
        return x;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    segtree seg(n);
    for(int i = 0; i < n; i++){
        char c; cin >> c;
        if(c == '0') seg.toggle(i);
    }
    vector<int> tg;
    vector<tuple<int, int, int>> query;
    for(int i = 0; i < q; i++){
        str tt; cin >> tt;
        if(tt == "toggle"){
            int in; cin >> in; in--;
            tg.pb(in);
        }
        else{
            int a, b; cin >> a >> b; a--, b-=2;
            query.pb({a, b, query.size()});
        }
    }
    map<pair<int, int>, int> mp;
    struct segment{
        int l, r, init, vl;
        bool closed;
        segment(int _l, int _r, int _init){
            l = _l, r = _r, init = _init, vl = -1, closed = 0;
        }
        void close(int e){
            vl = e-init+1;
            closed = 1;
        }
        bool operator<(segment a){
            return make_pair(r, l) < make_pair(a.r, a.l);
        }
    };
    vector<segment> segments;
    auto seg_add = [&](int l, int r, int init){
        mp[{l, r}] = segments.size();
        segments.pb(segment(l, r, init));   
    };
    auto seg_rem = [&](int l, int r, int tt){
        int pos = mp[{l, r}];
        mp[{l, r}] = -1;
        segments[pos].close(tt);
    };
    int sss = -1, eee = 0;
    for(int i = 0; i < n; i++){
        if(seg.get(i) == 0){
            sss = -1;
            continue;
        }
        if(sss == -1) sss = i, eee = i-1;
        eee++;
        if(i != n-1 && seg.get(i+1) == 1) continue;
        seg_add(sss, eee, 0);
    }
    for(int tt = 1; tt <= tg.size(); tt++){
        int in = tg[tt-1];
        if(seg.get(in) == 0){
            if(in > 0 && seg.get(in-1) == 1){
                int l = seg.rfind(in-1);
                seg_rem(l, in-1, tt-1);
            }
            if(in+1 < n && seg.get(in+1) == 1){
                int r = seg.find(in+1);
                seg_rem(in+1, r, tt-1);
            }
            seg.toggle(in);
            int l = seg.rfind(in), r = seg.find(in);
            seg_add(l, r, tt);
        }
        else{
            int l = seg.rfind(in), r = seg.find(in);
            seg_rem(l, r, tt-1);
            seg.toggle(in);
            if(in > 0 && seg.get(in-1) == 1){
                int l = seg.rfind(in-1);
                seg_add(l, in-1, tt);
            }
            if(in+1 < n && seg.get(in+1) == 1){
                int r = seg.find(in+1);
                seg_add(in+1, r, tt);
            }
        }
    }
    //for(auto sg: segments) cerr << sg.l << " " << sg.r << " " << sg.init << " " << sg.closed << " d\n";
    vector<vector<int>> sg2(n);
    for(int i = 0; i < segments.size(); i++){
        if(segments[i].closed) continue;
        sg2[segments[i].l].pb(segments[i].r);
        segments[i].close(tg.size());
    }
    vector<vector<segment>> rrs(n);
    vector<vector<tuple<int, int, int>>> rrq(n);
    for(int i = 0; i < segments.size(); i++){
        rrs[segments[i].l].pb(segments[i]);
    }
    for(int i = 0; i < query.size(); i++) rrq[get<0>(query[i])].pb(query[i]);

    BIT bit(n);

    vector<ll> ans(query.size(), 0);
    for(int i = 0; i < n; i++){
        for(auto sg: rrs[i]) bit.upd(sg.r, sg.vl);
        for(auto [a, b, in]: rrq[i]) ans[in]+=bit.sum(b, n-1);
    }
    bit = BIT(n);
    for(int i = 0; i < n; i++){
        for(int r: sg2[i]) bit.upd(r, 1);
        for(auto [a, b, in]: rrq[i]) ans[in]+=bit.sum(b, n-1)*in;
    }
    for(ll x: ans) cout << x << "\n";
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int tt = 1; tt <= tg.size(); tt++){
      |                     ~~~^~~~~~~~~~~~
street_lamps.cpp:168:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for(int i = 0; i < segments.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int i = 0; i < segments.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int i = 0; i < query.size(); i++) rrq[get<0>(query[i])].pb(query[i]);
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 184 ms 14076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 351 ms 54244 KB Output is correct
6 Correct 568 ms 63464 KB Output is correct
7 Correct 658 ms 68580 KB Output is correct
8 Correct 943 ms 74336 KB Output is correct
9 Correct 261 ms 18992 KB Output is correct
10 Correct 247 ms 18136 KB Output is correct
11 Correct 263 ms 19040 KB Output is correct
12 Correct 248 ms 18120 KB Output is correct
13 Correct 303 ms 19032 KB Output is correct
14 Correct 252 ms 17932 KB Output is correct
15 Correct 281 ms 46476 KB Output is correct
16 Correct 295 ms 47952 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -