Submission #563688

#	Time	Username	Problem	Language	Result	Execution time	Memory
563688		jeqcho	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3353 ms	106844 KiB

street_lamps

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

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#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)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

struct query
{
	int t,a,b,qid,add;
	
	query(int _t,int _a,int _b,int _qid,int _add)
	{
		t=_t;a=_a;b=_b;qid=_qid;add=_add;
	}
};

template<class T>
struct segmentTree
{
    vector<T> seg;
    int arr_sz;
    T init_value = 0;
    // sum 0
    // min 1e9+3
    // max -(1e9+3)
    
    T comb(T a, T b)
    {
        return a+b;
//        return min(a,b);
//        return max(a,b);
        
    }
    void init(int n, vector<T> &arr)
    {
        int p2 = ceil(log2((long double)n));
        arr_sz = 1<<p2;
        int tree_sz = 2*arr_sz;
        seg.rsz(tree_sz);
        fill(all(seg),init_value);
        F0R(i,n)
        {
            seg[arr_sz-1 + i]=arr[i];
        }
        build(0,0,arr_sz);
    }

    T build(int idex, int lx, int rx)
    {
        if(lx==rx-1)return seg[idex];
        seg[idex] = comb(build(2*idex+1, lx,(lx+rx)/2 ), build(2*idex+2, (lx+rx)/2,rx));
        return seg[idex];
    }

    void update(int idex, T val)
    {
        idex += arr_sz-1;
        seg[idex] += val;
        while(idex>0)
        {
			--idex;
            idex /= 2;
            seg[idex] = comb(seg[2*idex+1], seg[2*idex+2]);
           
        }
    }
    
    T query(int l, int r)
    {
        return query(0,l,r,0,arr_sz);
    }

    T query(int idex, int lq, int rq, int lx, int rx)
    {
        if(lx>=lq&&rx<=rq)return seg[idex];
        else if(lx>=rq||rx<=lq) return init_value;
        else
        {
            return comb(query(2*idex+1,lq,rq, lx,(lx+rx)/2 ), query(2*idex+2,lq,rq, (lx+rx)/2,rx));
        }
    }
};



vi ans;
vector<query>queries;
segmentTree<int>seg;

void cdq(int lt, int rt)
{
	if(rt-lt==1)return;
	int mt=(lt+rt)/2;
	cdq(lt,mt); cdq(mt,rt);
	int lef=lt; int rig=mt;
	vector<query>tmp;
	vpi rollback;
	//cout<<"CDQ"<<' '<<lt<<' '<<rt<<'\n';
	while(lef<mt && rig < rt)
	{
		if(queries[lef].a <= queries[rig].a)
		{
			tmp.pb(queries[lef]);
			seg.update(queries[lef].b,queries[lef].add);
			rollback.pb({queries[lef].b,-queries[lef].add});
			++lef;
		}
		else
		{
			tmp.pb(queries[rig]);
			ans[queries[rig].qid]+=seg.query(0,queries[rig].b+1);
			//cout<<queries[rig].t<<' '<<queries[rig].b<<' '<<seg.query(0,queries[rig].b+1)<<'\n';
			++rig;
		}
	}
	while(lef<mt)
	{
		tmp.pb(queries[lef]);
		//seg.update(queries[lef].b,queries[lef].add);
		++lef;
	}
	while(rig<rt)
	{
		tmp.pb(queries[rig]);
		ans[queries[rig].qid]+=seg.query(0,queries[rig].b+1);
		++rig;
	}
	F0R(i,sz(tmp))
	{
		queries[lt+i]=tmp[i];
	}
	trav(e,rollback)
	{
		seg.update(e.fi,e.se);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,q;
	cin>>n>>q;
	string s1;
	cin>>s1;
	vector<bool>s(n);
	set<int>posz;
	F0R(i,n)
	{
		s[i]=s1[i]-'0';
		if(!s[i])posz.insert(i);
	}
	ans.pb(0);
	vi v(n+1,0);
	seg.init(n,v);
	posz.insert(n);
	posz.insert(-1);
	FOR(i,1,q+1)
	{
		string t;
		cin>>t;
		if(t=="toggle")
		{
			int x;
			cin>>x;
			--x;
			int lz=*(--posz.lower_bound(x));
			int rz=*posz.upper_bound(x);
			int sign;
			if(s[x])
			{
				// turn off
				sign=1;
				posz.insert(x);
			}
			else
			{
				sign=-1;
				posz.erase(x);
			}
			s[x]=!s[x];
			queries.pb(query(i,lz+1,x,0,i*sign));
			queries.pb(query(i,lz+1,rz,0,i*-sign));
			queries.pb(query(i,x+1,x,0,i*-sign));
			queries.pb(query(i,x+1,rz,0,i*sign));
		}
		else
		{
			int a,b;
			cin>>a>>b;
			--a;--b;
			queries.pb(query(i,a,b-1,sz(ans),0));
			ans.pb(0);
			if(*posz.lower_bound(a)>b-1)
			{
				ans.back()+=i;
			}
		}
	}
	cdq(0,sz(queries));
	FOR(i,1,sz(ans))cout<<ans[i]<<'\n';
	return 0;
}

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