Submission #579504

#	Time	Username	Problem	Language	Result	Execution time	Memory
579504		josanneo22	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	384 ms	1212 KiB

street_lamps

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x<<'\n';
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;
void normal()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
}
char change(char x)
{
	if(x=='0') return '1';
	return '0';
}
int n, q;
/*sub3
 * vll v, t;
 
void build(int tl, int tr, int ind) 
{
	if (tl == tr) 
	{
		t[ind] = v[tl];
		return;
	}
	int mid = (tl + tr) / 2;
	build(tl, mid, 2 * ind);
	build(mid + 1, tr, 2 * ind + 1);
	t[ind] = max(t[2 * ind] ,t[2 * ind + 1]);
	return;
}
 
ll query(int tl, int tr, int ql, int qr, int ind) 
{
	if (tl >= ql and tr <= qr)
		return t[ind];
	
	if (tr < ql || tl > qr) 
		return -1LL;
 
	int mid = (tl + tr) / 2;
	ll left = query(tl, mid, ql, qr, 2 * ind);
	ll right = query(mid + 1, tr, ql, qr, 2 * ind + 1);
 
	return max(left, right);
}
 
void update(int tl, int tr, int p, int diff, int ind) 
{
	if (p < tl || p > tr) 
		return;
	if (tl == tr) 
	{
		t[ind] = diff;
		return;
	}
	int mid = (tl + tr) / 2;
	update(tl, mid, p, diff, 2 * ind);
	update(mid + 1, tr, p, diff, 2 * ind + 1);
 
	t[ind] = max(t[2 * ind] , t[2 * ind + 1]);
	return;
}

*/
void solve()
{
	cin>>n>>q;
	if(n<=100 && q<=100)
	{
		vpii queries(q);
		string ori;cin>>ori;
		
		FOR(i,0,q)
		{
			string x; cin>>x;
			if(x=="query")
			{
				int a,b;
				cin>>a>>b;
				a--;b--;
				queries[i]={a,b};
				int ans=0;
				string str=ori;
				FOR(j,0,i+1)
				{
					int cnt=0;
					FOR(k,a,b)
					{
						if(str[k]=='1') 
							cnt++;
					}
					if(cnt==(b-a))
						ans++;
					if(queries[j].s==-1) str[queries[j].f]=change(str[queries[j].f]);
				}
				out(ans);
			}
			else
			{
				int a;
				cin>>a;
				a--;
				queries[i]={a,-1};
			}
		}
	}
	else {
	string ori; 
	cin>>ori;
	int t[n][2];
	FOR(i,0,n) FOR(j,0,2) t[i][j]=0;
	FOR(i,1,q+1)
	{
		string type; cin>>type;
		if(type=="query")
		{
			int a,b; cin>>a>>b;
			a--;
			if(ori[a]==1)
			{
				cout<<t[a][0]+i-t[a][1]<<'\n';
			}
			else
				cout<<t[a][0]<<'\n';
		}
		else
		{
			int a; cin>>a;
			a--;
			if(ori[a]=='1')
			{
				t[a][0]+=i-t[a][1];
			}
			t[a][1]=i;
			if(ori[a]=='1') ori[a]='0';
			else ori[a]='1';
		}
	}
	}/*
	FOR(i,1,q+1)
	{
		string type; cin>>type;
		if(type=="query")
		{
			int a,b; cin>>a>>b;
			a--;
			if(ori[a]==1)
			{
				cout<<t[a].f+i-t[a].s<<'\n';
			}
			else
				cout<<t[a].f<<'\n';
		}
		else
		{
			int a; cin>>a;
			a--;
			if(ori[a]=='1')
			{
				t[a].f+=i-t[a].s;
			}
			t[a].s=i;
			if(ori[a]=='1') ori[a]='0';
			else ori[a]='1';
		}
	}
	else if(
	v.rsz(n);
	FOR(i,0,n)
	{
		if(ori[i]=='0') v[i]=INT_MAX;
		else 
			v[i]==0LL;
	}
	t.resize(4 * n + 2);
	build(0, n - 1, 1);
	FOR(i,1,q+1)
	{
		string type; cin>>type;
		if(type=="query")
		{
			int a,b; cin>>a>>b;
			ll x=query(0,n-1,a-1,b-2,1);
			if(x==INT_MAX) cout<<"0\n";
			else cout<<i-x<<endl;
			
		}
		else
		{
			int a; cin>>a;
			if(ori[a]=='0')
			{
				update(0,n-1,a,i,0);
			}
		}
	}
	*/
	return;
}
int main()
{
	solve();
	return 0;
}

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