oj.uz

Submission #563688

# Submission time Handle Problem Language Result Execution time Memory
563688 2022-05-18T02:06:58 Z jeqcho Street Lamps (APIO19_street_lamps) C++17
100 / 100
 3353 ms 106844 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 54340 KB Output is correct
2 Correct 1071 ms 54668 KB Output is correct
3 Correct 1422 ms 55336 KB Output is correct
4 Correct 2094 ms 69064 KB Output is correct
5 Correct 1843 ms 62484 KB Output is correct
6 Correct 2310 ms 72012 KB Output is correct
7 Correct 1091 ms 49848 KB Output is correct
8 Correct 865 ms 35900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 5 ms 536 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3353 ms 106844 KB Output is correct
6 Correct 2593 ms 73260 KB Output is correct
7 Correct 1930 ms 59832 KB Output is correct
8 Correct 955 ms 35832 KB Output is correct
9 Correct 282 ms 19028 KB Output is correct
10 Correct 317 ms 25980 KB Output is correct
11 Correct 338 ms 25920 KB Output is correct
12 Correct 1157 ms 49856 KB Output is correct
13 Correct 935 ms 35900 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 548 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 1109 ms 43212 KB Output is correct
6 Correct 1740 ms 62440 KB Output is correct
7 Correct 2354 ms 72112 KB Output is correct
8 Correct 3216 ms 105060 KB Output is correct
9 Correct 1351 ms 62244 KB Output is correct
10 Correct 1431 ms 90968 KB Output is correct
11 Correct 1339 ms 62212 KB Output is correct
12 Correct 1441 ms 90700 KB Output is correct
13 Correct 1354 ms 62252 KB Output is correct
14 Correct 1433 ms 90760 KB Output is correct
15 Correct 1147 ms 49992 KB Output is correct
16 Correct 944 ms 35712 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 929 ms 54340 KB Output is correct
9 Correct 1071 ms 54668 KB Output is correct
10 Correct 1422 ms 55336 KB Output is correct
11 Correct 2094 ms 69064 KB Output is correct
12 Correct 1843 ms 62484 KB Output is correct
13 Correct 2310 ms 72012 KB Output is correct
14 Correct 1091 ms 49848 KB Output is correct
15 Correct 865 ms 35900 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 5 ms 536 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 3353 ms 106844 KB Output is correct
21 Correct 2593 ms 73260 KB Output is correct
22 Correct 1930 ms 59832 KB Output is correct
23 Correct 955 ms 35832 KB Output is correct
24 Correct 282 ms 19028 KB Output is correct
25 Correct 317 ms 25980 KB Output is correct
26 Correct 338 ms 25920 KB Output is correct
27 Correct 1157 ms 49856 KB Output is correct
28 Correct 935 ms 35900 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 4 ms 548 KB Output is correct
32 Correct 5 ms 596 KB Output is correct
33 Correct 1109 ms 43212 KB Output is correct
34 Correct 1740 ms 62440 KB Output is correct
35 Correct 2354 ms 72112 KB Output is correct
36 Correct 3216 ms 105060 KB Output is correct
37 Correct 1351 ms 62244 KB Output is correct
38 Correct 1431 ms 90968 KB Output is correct
39 Correct 1339 ms 62212 KB Output is correct
40 Correct 1441 ms 90700 KB Output is correct
41 Correct 1354 ms 62252 KB Output is correct
42 Correct 1433 ms 90760 KB Output is correct
43 Correct 1147 ms 49992 KB Output is correct
44 Correct 944 ms 35712 KB Output is correct
45 Correct 440 ms 32604 KB Output is correct
46 Correct 607 ms 32868 KB Output is correct
47 Correct 1213 ms 37828 KB Output is correct
48 Correct 2152 ms 68908 KB Output is correct
49 Correct 395 ms 27772 KB Output is correct
50 Correct 361 ms 27752 KB Output is correct
51 Correct 401 ms 27968 KB Output is correct
52 Correct 435 ms 28204 KB Output is correct
53 Correct 433 ms 28168 KB Output is correct
54 Correct 424 ms 28228 KB Output is correct