Submission #498720

#	Time	Username	Problem	Language	Result	Execution time	Memory
498720		Karliver	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3273 ms	72312 KiB

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20