Submission #563208

#	Time	Username	Problem	Language	Result	Execution time	Memory
563208		josanneo22	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5064 ms	3888 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 duplicate(vi arr)
{
	arr.erase(unique(all(arr)),arr.end());
}
 
void file_in(string s)
{
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}
boost::math::lcm(10,20) 
*/
/*CONVEX HULL 

int orientation(pii p, pii q, pii r)
{
    int val = (q.s - p.s) * (r.f - q.f) - (q.f - p.f) * (r.s - q.s);
 
    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}
vpii hull;
void convexHull(pii points[], int n)
{
    if (n < 3) 
    {
	    FOR(i,0,n)
	    	FOR(j,0,n)
	    	{
	    		if(i==j)continue;
	    		
	    	}
	}
    int l = 0;
    FOR(i,1,n)
        if (points[i].f < points[l].f)
            l = i;
    int p = l, q;
    do
    {
        hull.push_back(points[p]);
        q = (p+1)%n;
        FOR(i,0,n)
        {
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
        }
        p = q;
    } while (p != l); 
}
 
int main()
{
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    convexHull(points, n);
}
*/
/* RMQ with sparse
int lookup[MAX][MAX];
struct Query 
{
    int L, R;
};
 
void preprocess(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        lookup[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 0; (i + (1 << j) - 1) < n; i++)
        {
            if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
                lookup[i][j] = lookup[i][j - 1];
            else
                lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
        }
    }
}
 
int query(int arr[], int L, int R)
{
    int j = (int)log2(R - L + 1);
    if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]])
        return arr[lookup[L][j]];
    else
        return arr[lookup[R - (1 << j) + 1][j]];
}
 
void RMQ(int arr[], int n, Query q[], int m)
{
    preprocess(arr, n);
    FOR(i,0,m)
    {
        int L = q[i].L, R = q[i].R;
        cout << query(arr, L, R) << endl;
    }
}
 
// Driver code
int main()
{
    int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    Query q[] = { { 0, 4 }, { 4, 7 }, { 7, 8 } };
    int m = sizeof(q) / sizeof(q[0]);
    RMQ(a, n, q, m);
    return 0;
}
*/
void normal()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
}
 
ll ex(int base, int power)
{
	if (power == 0)
		return 1;
	ll result = ex(base, power / 2);
	if (power % 2 == 1)
		return(((result * result) % mod) * base) % mod;
	else return (result * result) % mod;
}
char change(char x)
{
	if(x=='0') return '1';
	return '0';
}
	
void solve()
{
	int n,q;
	cin>>n>>q;
	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};
		}
	}
}
int main()
{
	normal();
	int t=1;
	while(t--)
	{
		solve();
	}
	return 0;
}

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