oj.uz

Submission #908164

# Submission time Handle Problem Language Result Execution time Memory
908164 2024-01-16T08:55:53 Z Boycl07 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1456 ms 25020 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task ""
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)
 
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
 
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
 
 
const int N =  3e5 + 10;
const int M = 1e3 + 3;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const ll LINF = 1e17 + 2;
const int block_size = 500;
const int LOG = 29;
const int offset = N;
const int LIM = 1e4 ;
const int AL = 26;
 
int n, q;

struct fenwick
{
    int bit[N];

    void update(int u, int v) {for(; u <= n + 1; u += u & -u) bit[u] += v;}
    int get(int u) {int res = 0; for(; u; u -= u & -u) res += bit[u]; return res;}

    int find_left(int x)
    {
        int v = get(x);
        int pos = 0;
        ford(i, LOG, 0)
            if(pos + (1 << i) <= n + 1 && v - bit[pos + (1 << i)] > 0)
                pos |= 1 << i, v -= bit[pos];
        return pos + 1;
    }
    int find_right(int x)
    {
        int v = get(x);
        int pos = 0;
        ford(i, LOG, 0)
            if(pos + (1 << i) <= n + 1 && v - bit[pos + (1 << i)] >= 0)
                pos |= 1 << i, v -= bit[pos];
        return pos;
    }
} sum, cnt;

char t[N];

int ans[N];

int queries[N][3];

void cdq(int l, int r)
{
    if(l > r) return;
    if(l == r)
    {
        if(queries[l][0])
            if(cnt.get(queries[l][2]) - cnt.get(queries[l][1]) == 0)
                ans[l] += l;
        return;
    }

    int mid = l + r >> 1;

    cdq(l, mid);

    vector<array<int, 3>> ask_right;
    vector<array<int, 3>> segments;
    forn(i, max(1, l) , mid)
        if(queries[i][0] == 0)
        {
            int x = queries[i][1];
            int u = cnt.find_left(x);
            int v = cnt.find_right(x + 1);
            int val = t[x] == '0' ? -1 : 1;
            t[x] ^= 1;
            segments.pb({u, v, val * i});
            segments.pb({u, x, -val * i});
            segments.pb({x + 1, v, -val * i});
            cnt.update(x + 1, val);
        }
    forn(i, mid + 1, r) if(queries[i][0])
        ask_right.pb({queries[i][1], queries[i][2], i});
    sort(all(ask_right), [] (const array<int, 3> x, const array<int, 3> y) {
        return make_pair(x[1], x[0]) > make_pair(y[1], y[0]);
    });
    sort(all(segments), [] (const array<int, 3> x, const array<int, 3> y) {
        return make_pair(x[1], x[0]) > make_pair(y[1], y[0]);
    });
    int j = 0;
    for(auto &[l, r, idx] : ask_right)
    {
        while(j < sz(segments) && segments[j][1] >= r)
            sum.update(segments[j][0], segments[j][2]), ++j;
        ans[idx] += sum.get(l);
    }
    forn(k, 0, j - 1)
        sum.update(segments[k][0], -segments[k][2]);
    
    cdq(mid + 1, r);

    forn(i, max(1, l) , mid)
    if(queries[i][0] == 0)
        {
            int x = queries[i][1];
            int val = t[x] == '0' ? -1 : 1;
            t[x] ^= 1;
            cnt.update(x + 1, val);
        }

}


void solve()
{
    cin >> n >> q;
    rep(i, n) cin >> t[i];
    rep(i, q)
    {
        string s;
        cin >> s;
        if(s[0] == 'q')
        {
            queries[i][0] = 1;
            cin >> queries[i][1] >> queries[i][2];
        }
        else queries[i][0] = 0, cin >> queries[i][1];
    }

    rep(i, n) if(t[i] == '0') cnt.update(i + 1, 1);


    cdq(0, q);
    rep(i, q) if(queries[i][0]) cout << ans[i] << endl;
    
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int TC = 1;
 
 
    while(TC--)
    {
        solve();
        cout << endl;
    }
 
    return 0;
}
//ha

Compilation message

street_lamps.cpp: In function 'void cdq(int, int)':
street_lamps.cpp:90:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 14552 KB Output is correct
2 Correct 631 ms 18168 KB Output is correct
3 Correct 728 ms 18292 KB Output is correct
4 Correct 948 ms 20684 KB Output is correct
5 Correct 810 ms 20680 KB Output is correct
6 Correct 1004 ms 23560 KB Output is correct
7 Correct 273 ms 17224 KB Output is correct
8 Correct 276 ms 17540 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1456 ms 24484 KB Output is correct
6 Correct 1200 ms 23808 KB Output is correct
7 Correct 813 ms 19968 KB Output is correct
8 Correct 305 ms 17268 KB Output is correct
9 Correct 174 ms 12300 KB Output is correct
10 Correct 198 ms 15472 KB Output is correct
11 Correct 199 ms 14752 KB Output is correct
12 Correct 304 ms 18528 KB Output is correct
13 Correct 303 ms 18436 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4616 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 319 ms 18672 KB Output is correct
6 Correct 701 ms 23416 KB Output is correct
7 Correct 1020 ms 23580 KB Output is correct
8 Correct 1338 ms 25020 KB Output is correct
9 Correct 772 ms 23340 KB Output is correct
10 Correct 831 ms 22116 KB Output is correct
11 Correct 771 ms 23260 KB Output is correct
12 Correct 831 ms 23124 KB Output is correct
13 Correct 772 ms 22532 KB Output is correct
14 Correct 837 ms 22536 KB Output is correct
15 Correct 309 ms 18172 KB Output is correct
16 Correct 301 ms 17324 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 596 ms 14552 KB Output is correct
9 Correct 631 ms 18168 KB Output is correct
10 Correct 728 ms 18292 KB Output is correct
11 Correct 948 ms 20684 KB Output is correct
12 Correct 810 ms 20680 KB Output is correct
13 Correct 1004 ms 23560 KB Output is correct
14 Correct 273 ms 17224 KB Output is correct
15 Correct 276 ms 17540 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 3 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Correct 2 ms 4440 KB Output is correct
20 Correct 1456 ms 24484 KB Output is correct
21 Correct 1200 ms 23808 KB Output is correct
22 Correct 813 ms 19968 KB Output is correct
23 Correct 305 ms 17268 KB Output is correct
24 Correct 174 ms 12300 KB Output is correct
25 Correct 198 ms 15472 KB Output is correct
26 Correct 199 ms 14752 KB Output is correct
27 Correct 304 ms 18528 KB Output is correct
28 Correct 303 ms 18436 KB Output is correct
29 Correct 2 ms 4444 KB Output is correct
30 Correct 2 ms 4444 KB Output is correct
31 Correct 2 ms 4616 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Correct 319 ms 18672 KB Output is correct
34 Correct 701 ms 23416 KB Output is correct
35 Correct 1020 ms 23580 KB Output is correct
36 Correct 1338 ms 25020 KB Output is correct
37 Correct 772 ms 23340 KB Output is correct
38 Correct 831 ms 22116 KB Output is correct
39 Correct 771 ms 23260 KB Output is correct
40 Correct 831 ms 23124 KB Output is correct
41 Correct 772 ms 22532 KB Output is correct
42 Correct 837 ms 22536 KB Output is correct
43 Correct 309 ms 18172 KB Output is correct
44 Correct 301 ms 17324 KB Output is correct
45 Correct 332 ms 15188 KB Output is correct
46 Correct 400 ms 14160 KB Output is correct
47 Correct 552 ms 15344 KB Output is correct
48 Correct 945 ms 20540 KB Output is correct
49 Correct 217 ms 15480 KB Output is correct
50 Correct 217 ms 15560 KB Output is correct
51 Correct 223 ms 14956 KB Output is correct
52 Correct 207 ms 16028 KB Output is correct
53 Correct 216 ms 15276 KB Output is correct
54 Correct 207 ms 16248 KB Output is correct