답안 #498720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498720	2021-12-26T09:03:53 Z	Karliver	가로등 (APIO19_street_lamps)	C++17	100 / 100	3273 ms	72312 KB

street_lamps

	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;
const int mxn = 3e5+2;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}

template<typename Data>
struct FenwickTree { // Range Update & Point Query
    int N;
    vector<Data> Tree;
 
    FenwickTree() { N = 0; Tree.clear(); }
 
    /* Standard Tree Updates */
    void resize(int n) {
        N = n;
        Tree.resize(N + 1);
    }
 
    void update_tree(int p, Data x) {
        for (int i = p; i <= N; i += i & -i) {
            Tree[i] += x;
        }
    }
 
    /* Range Update & Point Query */
    void update(int l, int r, Data x) {
        update_tree(l, x); // Update Prefix Difference
        update_tree(r + 1, -x); // Update Prefix Difference
    }
 
    Data query(int p) {
        Data res = 0;
        for (int i = p; i > 0; i -= i & -i) {
            res += Tree[i];
        }
        return res;
    }
 
};
 
template<typename Data>
struct FenwickTree2D { // 2D Range Update & Point Query
    int N;
    vector<vector<Data>> Coordinate;
    vector<FenwickTree<Data>> Tree;
 
    FenwickTree2D() { N = 0; Tree.clear(); }
    FenwickTree2D(int n) { N = n; resize(n); }
 
    /* Standard Tree Updates */
    void build() {
        for (int i = 1; i <= N; i++) {
            sort(begin(Coordinate[i]), end(Coordinate[i]));
            Coordinate[i].resize(unique(begin(Coordinate[i]), end(Coordinate[i])) - begin(Coordinate[i]));
            Tree[i].resize(Coordinate[i].size());
        }
    }
 
    void resize(int n) {
        N = n;
        Tree.resize(n + 1);
        Coordinate.resize(n + 1);
    }
 
    void insert_query_interval(int a, int b) {
        for (int i = a; i > 0; i -= i & -i) {
            Coordinate[i].emplace_back(b);
        }
    }
 
    void update_tree(int p, int l, int r, Data x) {
        for (int i = p; i <= N; i += i & -i) {
            int idx_l = lower_bound(begin(Coordinate[i]), end(Coordinate[i]), l) - begin(Coordinate[i]) + 1; // first element that is >= l
            int idx_r = prev(upper_bound(begin(Coordinate[i]), end(Coordinate[i]), r)) - begin(Coordinate[i]) + 1; // last element that is <= r
            Tree[i].update(idx_l, idx_r, x);
        }
    }
 
    /* 2D Range Update & Point Query Functions */
    void update(int lo, int hi, int l, int r, Data x) { // Range update rectangle (lo...hi) * (l...r)
        update_tree(lo, l, r, x); // Update Prefix Difference
        update_tree(hi + 1, l, r, -x); // Update Prefix Difference
    }
 
    Data query(int r, int c) {
        Data res = 0;
        for (int i = r; i > 0; i -= i & -i) {
            int idx = prev(upper_bound(begin(Coordinate[i]), end(Coordinate[i]), c)) - begin(Coordinate[i]) + 1; // last element that is <= r
            res += Tree[i].query(idx);
        }
        return res;
    }
 
};
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)


void solve() {

	int n, q;
	cin >> n >> q;

	string s;
	cin >> s;
	
	FenwickTree2D<int> F2;
	F2.resize(n+1);
	V<pair<string, pair<int, int>>> E;
	forn(i, q) {
		string type;
		cin >> type;
		if(type == "toggle") {
			int x;
			cin >> x;
			E.push_back({type, {x, 0}});
		}
		else {
			int l, r;
			cin >> l >> r;
			
			E.push_back({type, {l, r-1}});
			F2.insert_query_interval(l, r-1);
		}
	}
	F2.build();
	FenwickTree<int> F1;
	F1.resize(n+1);

	forn(i, n) if(s[i] == '1')F1.update_tree(i+1, 1);
	int Q = 1;

	for(auto &[tt, gs] : E) {
		auto [l, r] = gs;

		if(tt == "toggle") {
			int low = 0;
			int high = n-l;
				
			while(low < high) {
				int m = (low + high+1) / 2;
				int need = m+(s[l-1]=='1');
				if(F1.query(l+m)-F1.query(l-1)==need)
					low = m;
				else high = m-1;
			}
			
			int Rbor = l+low;
			low = 0;
			high = l-1;
			while(low < high) {
				int m = (low + high+1) / 2;
				int need = m+(s[l-1]=='1');
				if(F1.query(l)-F1.query(l-m-1)==need)
					low = m;
				else
					high = m - 1;
			}
			int Lbor = l-low;

			if(s[l-1] == '1') {
				s[l-1] = '0';
				F1.update_tree(l, -1);
				F2.update(Lbor, l, l, Rbor, Q);
			}
			else {
				s[l-1] = '1';
				F1.update_tree(l,1);
				F2.update(Lbor, l, l, Rbor, -Q);
			}
			debug(Lbor, Rbor);
			
		}
		else {
			int sm = F2.query(l, r);
			//debug(sm);
			if(F1.query(r)-F1.query(l-1)==r-l+1)
				sm += Q;
			cout << sm << '\n';
		}
		++Q;
	}
	

}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1

20.0 / 20.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1559 ms	26000 KB	Output is correct
2	Correct	1607 ms	26596 KB	Output is correct
3	Correct	1740 ms	28604 KB	Output is correct
4	Correct	2348 ms	63572 KB	Output is correct
5	Correct	2305 ms	65788 KB	Output is correct
6	Correct	2476 ms	61840 KB	Output is correct
7	Correct	892 ms	69476 KB	Output is correct
8	Correct	960 ms	71080 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	588 KB	Output is correct
2	Correct	8 ms	460 KB	Output is correct
3	Correct	5 ms	452 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	3185 ms	53464 KB	Output is correct
6	Correct	2915 ms	59768 KB	Output is correct
7	Correct	2219 ms	64972 KB	Output is correct
8	Correct	937 ms	72312 KB	Output is correct
9	Correct	127 ms	17228 KB	Output is correct
10	Correct	148 ms	27800 KB	Output is correct
11	Correct	186 ms	28204 KB	Output is correct
12	Correct	910 ms	70788 KB	Output is correct
13	Correct	994 ms	72136 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	4 ms	460 KB	Output is correct
3	Correct	6 ms	460 KB	Output is correct
4	Correct	12 ms	440 KB	Output is correct
5	Correct	1027 ms	70608 KB	Output is correct
6	Correct	1634 ms	66508 KB	Output is correct
7	Correct	2404 ms	61552 KB	Output is correct
8	Correct	3273 ms	53468 KB	Output is correct
9	Correct	2130 ms	24728 KB	Output is correct
10	Correct	2560 ms	23744 KB	Output is correct
11	Correct	2110 ms	24828 KB	Output is correct
12	Correct	2565 ms	23800 KB	Output is correct
13	Correct	2011 ms	24768 KB	Output is correct
14	Correct	2573 ms	23736 KB	Output is correct
15	Correct	878 ms	70964 KB	Output is correct
16	Correct	877 ms	72220 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	308 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1559 ms	26000 KB	Output is correct
9	Correct	1607 ms	26596 KB	Output is correct
10	Correct	1740 ms	28604 KB	Output is correct
11	Correct	2348 ms	63572 KB	Output is correct
12	Correct	2305 ms	65788 KB	Output is correct
13	Correct	2476 ms	61840 KB	Output is correct
14	Correct	892 ms	69476 KB	Output is correct
15	Correct	960 ms	71080 KB	Output is correct
16	Correct	12 ms	588 KB	Output is correct
17	Correct	8 ms	460 KB	Output is correct
18	Correct	5 ms	452 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	3185 ms	53464 KB	Output is correct
21	Correct	2915 ms	59768 KB	Output is correct
22	Correct	2219 ms	64972 KB	Output is correct
23	Correct	937 ms	72312 KB	Output is correct
24	Correct	127 ms	17228 KB	Output is correct
25	Correct	148 ms	27800 KB	Output is correct
26	Correct	186 ms	28204 KB	Output is correct
27	Correct	910 ms	70788 KB	Output is correct
28	Correct	994 ms	72136 KB	Output is correct
29	Correct	2 ms	460 KB	Output is correct
30	Correct	4 ms	460 KB	Output is correct
31	Correct	6 ms	460 KB	Output is correct
32	Correct	12 ms	440 KB	Output is correct
33	Correct	1027 ms	70608 KB	Output is correct
34	Correct	1634 ms	66508 KB	Output is correct
35	Correct	2404 ms	61552 KB	Output is correct
36	Correct	3273 ms	53468 KB	Output is correct
37	Correct	2130 ms	24728 KB	Output is correct
38	Correct	2560 ms	23744 KB	Output is correct
39	Correct	2110 ms	24828 KB	Output is correct
40	Correct	2565 ms	23800 KB	Output is correct
41	Correct	2011 ms	24768 KB	Output is correct
42	Correct	2573 ms	23736 KB	Output is correct
43	Correct	878 ms	70964 KB	Output is correct
44	Correct	877 ms	72220 KB	Output is correct
45	Correct	954 ms	13752 KB	Output is correct
46	Correct	1049 ms	14448 KB	Output is correct
47	Correct	1377 ms	31244 KB	Output is correct
48	Correct	2214 ms	63108 KB	Output is correct
49	Correct	160 ms	27992 KB	Output is correct
50	Correct	153 ms	27896 KB	Output is correct
51	Correct	161 ms	28332 KB	Output is correct
52	Correct	189 ms	29592 KB	Output is correct
53	Correct	199 ms	29680 KB	Output is correct
54	Correct	202 ms	29544 KB	Output is correct