Submission #1262438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262438		_rain_	Street Lamps (APIO19_street_lamps)	C++20	60 / 100	190 ms	19468 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))

template<class T1,class T2>	
	bool maximize(T1 &a,T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1,class T2>	
	bool minimize(T1 &a,T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T1>
	void compress(vector<T1>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1,class T2>
	int Find(vector<T1>&data,T2 x){
		return upper_bound(data.begin() , data.end() , x) - data.begin();
	}

const int N = (int) 3e5 + 1;
	int a[N + 2] = {} , b[N + 2] = {};
	bool state[N + 2] = {};
	int n , q;
	
	struct Question{
		string req;
		int a , b;
		void read(){
			cin >> req;
			if (req == "toggle") cin >> a;
			if (req == "query") cin >> a >> b;
			return;
		}
	} queri[N + 2];
	
namespace subtask1{	
	bool check(){
		return n <= 100 && q <= 100;
	}
	
	const int maxn = (int) 100;
		int cnt[maxn + 2][maxn + 2] = {};
	
	void calc(){
		for(int i = 1; i <= n; ++i){
			++cnt[i][i];
			for(int j = i; j <= n; ++j) {
				if (state[j]) cnt[i][j+1]++;
				else break;
			}
		}
		return;
	}
	
	void main_code(){
		calc();
		for(int i = 1; i <= q; ++i){
			if (queri[i].req == "toggle") state[queri[i].a] = !state[queri[i].a];
			if (queri[i].req == "query") cout << cnt[queri[i].a][queri[i].b] << '\n';
			calc();
		}
		return;
	}
	
};

namespace subtask2{
	bool check(){
		for(int i = 1; i <= n; ++i){
			if (queri[i].req == "query" && queri[i].b - queri[i].a !=1) return false;
		}
		return true;
	}
	
	int last[N + 2] = {};
	int sum[N + 2] = {};
	
	void main_code(){
		for(int i = 1; i <= n; ++i){
			if (state[i]) last[i] = 0; else last[i] = -1;
		}
		for(int i = 1; i <= q; ++i){
			if (queri[i].req == "toggle"){
				int id = queri[i].a;
				if (state[id]) {
					sum[id] += i - last[id] - 0;
					last[id] = -1;
				}
				else last[id] = i;
				state[id] = !state[id];
			}		
			if (queri[i].req == "query"){
				int a = queri[i].a , b = queri[i].b;
				if (state[a]==false) cout << sum[a] << '\n';
					else cout << sum[a] + (i - last[a]) << '\n';
			}
		}
	}
}

namespace subtask3{
	bool check(){
		vector<bool> tmp_state(n + 2 , 0);
		for(int i = 1; i <= n; ++i) tmp_state[i] = state[i];
		for(int i = 1; i <= n; ++i){
			if (queri[i].req == "toggle"){
				if (tmp_state[queri[i].a] == 1) return false;
				tmp_state[queri[i].a] = !tmp_state[queri[i].a];
			}
		}
		return true;
	}
	
	const int inf = (int) 1e9 + 7;
	int st[N * 4 + 2] = {};
	
		void update(int id , int l , int r , int p , int val){
			if (l == r) st[id] = val;
			else{
				int m = (l + r) / 2;
				if (p <= m)	update(id * 2 , l , m , p , val);
				else 
					update(id * 2 + 1 , m + 1 , r , p , val);
				st[id] = max(st[id * 2] , st[id * 2 + 1]);
			}
			return;
		}
		int Get(int id , int l , int r , int u , int v){
			if (l > v || r < u) return 0;
			if (u <= l && r <= v) return st[id];
			int m = (l + r) / 2;
			return max(Get(id * 2 , l , m , u , v) , Get(id * 2 + 1 , m + 1 , r , u , v));
		}
	
	void main_code(){
		memset(st , 0x3f , sizeof st);
		for(int i = 1; i <= n; ++i) if (state[i] == 1) update(1 , 1 , n , i , 0);
		for(int i = 1; i <= q; ++i) {
			if (queri[i].req == "toggle") update(1 , 1 , n , queri[i].a , i);
			else {
				int l = queri[i].a , r = queri[i].b;
				int x = max(0 , i - Get(1,1,n,l,r-1));
				cout << x << '\n';
			}
		}
		
		return;
	}
}

namespace subtask4{
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> q;
		string s; cin >> s ; s = '#' + s;
		for(int i = 1; i <= n; ++i) state[i] = (s[i] == '0' ? 0 : 1);
		for(int i = 1; i <= q; ++i) queri[i].read();
		if (subtask1::check()) return subtask1::main_code() , 0;
		if (subtask2::check()) return subtask2::main_code() , 0;
		if (subtask3::check()) return subtask3::main_code() , 0;
		assert(false);
	return 0;
}

Compilation message (stderr)

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

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