oj.uz

Submission #530669

# Submission time Handle Problem Language Result Execution time Memory
530669 2022-02-26T10:21:58 Z Killer2501 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1273 ms 87920 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const int inf = 1e9;
int m, n, t, b[N], d[N], lab[N], c[N];
int k, a[N], dp[N], lst[N], fe[N];
int ans, tong;
vector<int> adj[N], g[N];
vector<int> vi;
string s;
bool vis[N];
struct BIT
{
    int n;
    vector<int> val, fe;
    BIT(){}
    void init()
    {
        sort(val.begin(), val.end());
        val.erase(unique(val.begin(), val.end()), val.end());
        fe.resize(val.size(), 0);
    }
    void add(int id, int x)
    {
        for(; id <= (int)val.size(); id += id & -id)fe[id-1] += x;
    }
    void add(int l, int r, int x)
    {
        if(val.empty())return;
        add(lower_bound(val.begin(), val.end(), l) - val.begin() + 1, x);
        add(upper_bound(val.begin(), val.end(), r) - val.begin() + 1, -x);
    }
    int get(int id)
    {
        int res = 0;
        for(id = upper_bound(val.begin(), val.end(), id) - val.begin(); id; id -= id & -id)res += fe[id-1];
        return res;
    }
}bit[N];
void fakeget(int l, int r)
{
    for(; l; l -= l & -l)
        bit[l].val.pb(r);
}
int get(int l, int r)
{
    int res = 0;
    for(; l; l -= l & -l)res += bit[l].get(r);
    return res;
}
void update(int id, int u, int v, int x)
{
    for(; id <= n; id += id & -id)bit[id].add(u, v, x);
}
void update(int l, int r, int u, int v, int x)
{
    update(l, u, v, x);
    update(r+1, u, v, -x);
}
void sol()
{
    cin >> n >> m >> s;
    set<int> st;
    st.insert(0);
    st.insert(n+1);
    for(int i = 1; i <= n; i ++)
    {
        if(s[i-1] == '0')
        {
            st.insert(i);
            c[i] = 1;
        }
    }
    for(int i = 1; i <= m; i ++)
    {
        cin >> s;
        if(s[0] == 'q')
        {
            d[i] = 1;
            cin >> a[i] >> b[i];
            --b[i];
            fakeget(a[i], b[i]);
        }
        else cin >> a[i];
    }
    for(int i = 1; i <= n; i ++)bit[i].init();
    for(int i = 1; i <= m; i ++)
    {
        if(d[i])
        {
            ans = get(a[i], b[i]);
            auto it = st.lower_bound(a[i]);
            if((*it) > b[i])ans += i;
            cout << ans << '\n';
        }
        else
        {
            if(c[a[i]])
            {
                auto it = st.lower_bound(a[i]);
                update(*prev(it)+1, a[i], a[i], *next(it)-1, -i);
                st.erase(a[i]);
            }
            else
            {
                st.insert(a[i]);
                auto it = st.lower_bound(a[i]);
                update(*prev(it)+1, a[i], a[i], *next(it)-1, i);
            }
            c[a[i]] ^= 1;
        }
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:133:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:134:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30796 KB Output is correct
2 Correct 17 ms 30796 KB Output is correct
3 Correct 16 ms 30868 KB Output is correct
4 Correct 15 ms 30796 KB Output is correct
5 Correct 17 ms 30884 KB Output is correct
6 Correct 19 ms 30876 KB Output is correct
7 Correct 20 ms 30776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 37704 KB Output is correct
2 Correct 192 ms 37996 KB Output is correct
3 Correct 316 ms 39748 KB Output is correct
4 Correct 1038 ms 62604 KB Output is correct
5 Correct 1035 ms 64772 KB Output is correct
6 Correct 917 ms 58124 KB Output is correct
7 Correct 1240 ms 81232 KB Output is correct
8 Correct 873 ms 67532 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30924 KB Output is correct
2 Correct 17 ms 30892 KB Output is correct
3 Correct 17 ms 30904 KB Output is correct
4 Correct 20 ms 30868 KB Output is correct
5 Correct 551 ms 54848 KB Output is correct
6 Correct 892 ms 63336 KB Output is correct
7 Correct 966 ms 68580 KB Output is correct
8 Correct 838 ms 73796 KB Output is correct
9 Correct 145 ms 41124 KB Output is correct
10 Correct 131 ms 41636 KB Output is correct
11 Correct 133 ms 42136 KB Output is correct
12 Correct 1273 ms 87592 KB Output is correct
13 Correct 835 ms 73876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30924 KB Output is correct
2 Correct 16 ms 30844 KB Output is correct
3 Correct 17 ms 30936 KB Output is correct
4 Correct 18 ms 30860 KB Output is correct
5 Correct 1144 ms 80372 KB Output is correct
6 Correct 1034 ms 72200 KB Output is correct
7 Correct 890 ms 62528 KB Output is correct
8 Correct 541 ms 45716 KB Output is correct
9 Correct 229 ms 38128 KB Output is correct
10 Correct 186 ms 35088 KB Output is correct
11 Correct 223 ms 38084 KB Output is correct
12 Correct 161 ms 35084 KB Output is correct
13 Correct 224 ms 38088 KB Output is correct
14 Correct 169 ms 35112 KB Output is correct
15 Correct 1232 ms 87920 KB Output is correct
16 Correct 915 ms 73740 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30796 KB Output is correct
2 Correct 17 ms 30796 KB Output is correct
3 Correct 16 ms 30868 KB Output is correct
4 Correct 15 ms 30796 KB Output is correct
5 Correct 17 ms 30884 KB Output is correct
6 Correct 19 ms 30876 KB Output is correct
7 Correct 20 ms 30776 KB Output is correct
8 Correct 154 ms 37704 KB Output is correct
9 Correct 192 ms 37996 KB Output is correct
10 Correct 316 ms 39748 KB Output is correct
11 Correct 1038 ms 62604 KB Output is correct
12 Correct 1035 ms 64772 KB Output is correct
13 Correct 917 ms 58124 KB Output is correct
14 Correct 1240 ms 81232 KB Output is correct
15 Correct 873 ms 67532 KB Output is correct
16 Correct 16 ms 30924 KB Output is correct
17 Correct 17 ms 30892 KB Output is correct
18 Correct 17 ms 30904 KB Output is correct
19 Correct 20 ms 30868 KB Output is correct
20 Correct 551 ms 54848 KB Output is correct
21 Correct 892 ms 63336 KB Output is correct
22 Correct 966 ms 68580 KB Output is correct
23 Correct 838 ms 73796 KB Output is correct
24 Correct 145 ms 41124 KB Output is correct
25 Correct 131 ms 41636 KB Output is correct
26 Correct 133 ms 42136 KB Output is correct
27 Correct 1273 ms 87592 KB Output is correct
28 Correct 835 ms 73876 KB Output is correct
29 Correct 17 ms 30924 KB Output is correct
30 Correct 16 ms 30844 KB Output is correct
31 Correct 17 ms 30936 KB Output is correct
32 Correct 18 ms 30860 KB Output is correct
33 Correct 1144 ms 80372 KB Output is correct
34 Correct 1034 ms 72200 KB Output is correct
35 Correct 890 ms 62528 KB Output is correct
36 Correct 541 ms 45716 KB Output is correct
37 Correct 229 ms 38128 KB Output is correct
38 Correct 186 ms 35088 KB Output is correct
39 Correct 223 ms 38084 KB Output is correct
40 Correct 161 ms 35084 KB Output is correct
41 Correct 224 ms 38088 KB Output is correct
42 Correct 169 ms 35112 KB Output is correct
43 Correct 1232 ms 87920 KB Output is correct
44 Correct 915 ms 73740 KB Output is correct
45 Correct 83 ms 36544 KB Output is correct
46 Correct 148 ms 37056 KB Output is correct
47 Correct 530 ms 49160 KB Output is correct
48 Correct 1006 ms 66848 KB Output is correct
49 Correct 148 ms 42860 KB Output is correct
50 Correct 143 ms 42572 KB Output is correct
51 Correct 158 ms 43148 KB Output is correct
52 Correct 174 ms 45132 KB Output is correct
53 Correct 203 ms 45192 KB Output is correct
54 Correct 191 ms 45048 KB Output is correct