Submission #743938

#	Time	Username	Problem	Language	Result	Execution time	Memory
743938		ThMinh_	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2119 ms	93040 KiB

street_lamps

#include<bits/stdc++.h>
#define forin(i,a,b) for(int i=a;i<=b;++i)
#define fi first
#define la second
using namespace std;
const int N = 3e5 + 10;
int n, q;
vector<int> bit[N], tr[N];
bool a[N];
set<pair<int, int>> st;
struct query {
    string s;
    int i, a, b;
};
query d[N];
void fakeup(int f, int l) {
    while(f <= n + 1) {
        bit[f].push_back(l);
        f += f & -f;
    }
}
void fakeget(int f, int l) {
    while(f) {
        bit[f].push_back(l);
        f -= f & -f;
    }
}
void up(int f, int l, int val) {
    while(f <= n + 1) {
        int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1;
        while(y) {
            tr[f][y - 1] += val;
            y -= y & -y;
        }
        f += f & -f;
    }
}
int get(int f, int l) {
    int res = 0;
    while(f) {
        int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1;
        while(y <= bit[f].size()) {
            res += tr[f][y - 1];
            y += y & -y;
        }
        f -= f & -f;
    }
    return res;
}
void fakeadd(int f, int l) {
    fakeup(f, l + 1);
    st.insert({f, l});
}
void add(int f, int l, int val) {
    up(f, l + 1, val);
    st.insert({f, l});
}
int main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("Task.inp","r")) {
        freopen("Task.inp","r",stdin);
        freopen("WA.out","w",stdout);
    }
    cin>>n>>q;
    string s; cin>>s;
    s = " " + s;
    forin(i,1,n) a[i] = (s[i] == '1');
    int f = -1;
    forin(i,1,n + 1) {
        if(f == -1 && a[i]) f = i;
        if(f != -1 && !a[i]) {
            fakeadd(f, i - 1);
            f = -1;
        }
    }
    st.insert({-1, -1});
    st.insert({1e9, 1e9});
    forin(j,1,q) {
        cin>>d[j].s;
        string s = d[j].s;
        if(s[0] == 't') {
            int i; cin>>i;
            d[j].i = i;
            auto i1 = st.upper_bound({i, 1e9});
            auto i2 = i1--;
            pair<int, int> cur = *i1;
            pair<int, int> aft = *i2;
            if(cur.la + 1 < i && i < aft.fi - 1) fakeadd(i, i);
            else if(i == cur.la + 1 && i == aft.fi - 1) {
                st.erase(i1); fakeup(cur.fi, cur.la + 1);
                st.erase(i2); fakeup(aft.fi, aft.la + 1);
                fakeadd(cur.fi, aft.la);
            }
            else if(i == cur.la + 1) {
                st.erase(i1); fakeup(cur.fi, cur.la + 1);
                fakeadd(cur.fi, cur.la + 1);
            }
            else if(i == aft.fi - 1) {
                st.erase(i2); fakeup(aft.fi, aft.la + 1);
                fakeadd(aft.fi - 1, aft.la);
            }
            else if(i <= cur.la) {
                st.erase(i1); fakeup(cur.fi, cur.la + 1);
                if(cur.fi != aft.la) {
                    if(i == cur.fi) fakeadd(cur.fi + 1, cur.la);
                    else if(i == cur.la) fakeadd(cur.fi, cur.la - 1);
                    else {
                        fakeadd(cur.fi, i - 1);
                        fakeadd(i + 1, cur.la);
                    }
                }
            }
        }
        else {
            cin>>d[j].a>>d[j].b;
            fakeget(d[j].a, d[j].b);
        }
    }
    forin(i,1,n + 1) {
        sort(bit[i].begin(), bit[i].end());
        bit[i].resize(unique(bit[i].begin(), bit[i].end()) - bit[i].begin());
        tr[i].resize(bit[i].size());
    }
    while(!st.empty()) st.erase(st.begin());
    f = -1;
    forin(i,1,n + 1) {
        if(f == -1 && a[i]) f = i;
        if(f != -1 && !a[i]) {
            add(f, i - 1, q);
            f = -1;
        }
    }
    st.insert({-1, -1});
    st.insert({1e9, 1e9});
    forin(j,1,q) {
        string s = d[j].s;
        if(s[0] == 't') {
            int i = d[j].i;
            auto i1 = st.upper_bound({i, 1e9});
            auto i2 = i1--;
            pair<int, int> cur = *i1;
            pair<int, int> aft = *i2;
            int val = q - j;
            if(cur.la + 1 < i && i < aft.fi - 1) add(i, i, val);
            else if(i == cur.la + 1 && i == aft.fi - 1) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                st.erase(i2); up(aft.fi, aft.la + 1, -val);
                add(cur.fi, aft.la, val);
            }
            else if(i == cur.la + 1) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                add(cur.fi, cur.la + 1, val);
            }
            else if(i == aft.fi - 1) {
                st.erase(i2); up(aft.fi, aft.la + 1, -val);
                add(aft.fi - 1, aft.la, val);
            }
            else if(i <= cur.la) {
                st.erase(i1); up(cur.fi, cur.la + 1, -val);
                if(cur.fi != cur.la) {
                    if(i == cur.fi) add(cur.fi + 1, cur.la, val);
                    else if(i == cur.la) add(cur.fi, cur.la - 1, val);
                    else {
                        add(cur.fi, i - 1, val);
                        add(i + 1, cur.la, val);
                    }
                }
            }
        }
        else {
            int a = d[j].a, b = d[j].b;
            pair<int, int> it = *--st.upper_bound({a, 1e9});
            if(it.fi <= a && b <= it.la + 1) cout<<get(a, b) - (q - j)<<"\n";
            else cout<<get(a, b)<<"\n";
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int get(int, int)':
street_lamps.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(y <= bit[f].size()) {
      |               ~~^~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("Task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("WA.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20