oj.uz

Submission #379544

# Submission time Handle Problem Language Result Execution time Memory
379544 2021-03-18T13:57:28 Z AriaH Street Lamps (APIO19_street_lamps) C++11
100 / 100
 3793 ms 218100 KB 
/** I can do this all day **/
 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
 
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
 
ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
 
char C[N];
 
string s;
 
int n, q, tp[N], fir[N], sec[N], checking;
 
vector < ll > vec[N], F[2][N]; /// F[0][i] -> sigma -l + r, F[1][i] -> tedad l haye bedune r
 
set < pii > st;
 
void pre_add(int i, int r) { for(; i <= n; i += i & -i) { vec[i].push_back(r); } }
 
void prep()
{ 
	for(int i = 0; i <= n; i ++)
	{ 
		vec[i].push_back(-mod);
		sort(all(vec[i]));
		vec[i].resize(unique(all(vec[i])) - vec[i].begin());
		F[0][i].resize(SZ(vec[i]) + 5, 0);
		F[1][i].resize(SZ(vec[i]) + 5, 0);
	}
}
 
void pre_ins(int i)
{
	if(st.empty()) { st.insert(Mp(i, i)); pre_add(i, i); return; }
	auto it = st.lower_bound(Mp(i, 0));
	if(it == st.end())
	{
		it --; pii cu = *it;
		if(cu.S == i - 1) { st.erase(it); cu.S ++; st.insert(cu); pre_add(cu.F, cu.S); }
		else st.insert(Mp(i, i)), pre_add(i, i);
		return;
	}
	pii R = *it;
	if(it == st.begin())
	{
		if(R.F == i + 1) { st.erase(R); R.F --; st.insert(R); pre_add(R.F, R.S); }
		else st.insert(Mp(i, i)), pre_add(i, i);
		return;
	}
	auto it2 = it; it2 --; pii L = *it2;
	if(L.S + 1 == R.F - 1) { st.erase(L); st.erase(R); st.insert(Mp(L.F, R.S)); pre_add(L.F, R.S); }
	else if(L.S + 1 == i) { st.erase(L); st.insert(Mp(L.F, i)); pre_add(L.F, i); }
	else if(R.F == i + 1) { st.erase(R); st.insert(Mp(i, R.S)); pre_add(i, R.S); }
	else st.insert(Mp(i, i)), pre_add(i, i);
}
 
void pre_del(int i)
{
	auto it = st.upper_bound(Mp(i, mod));
	it --;
	pii cu = *it;
	st.erase(it);
	if(cu.F < i && i < cu.S)
	{
		st.insert(Mp(cu.F, i - 1)); pre_add(cu.F, i - 1);
		st.insert(Mp(i + 1, cu.S)); pre_add(i + 1, cu.S);
	}
	else if(cu.F == i && i < cu.S) st.insert(Mp(i + 1, cu.S)), pre_add(i + 1, cu.S);
	else if(cu.F < i && cu.S == i) st.insert(Mp(cu.F, i - 1)), pre_add(cu.F, i - 1);
}
 
void add(int i, int r, int Tp, int x)
{
	for(; i <= n; i += i & -i)
	{
		int id = lower_bound(all(vec[i]), r) - vec[i].begin();
		for(int j = id; j < SZ(vec[i]); j += j & -j)
		{
			F[Tp][i][j] += x;
		}
	}
}
 
ll get(int i, int r, int Tp)
{
	ll ret = 0;
	for(; i; i -= i & -i)
	{
		int id = lower_bound(all(vec[i]), r) - vec[i].begin();
		for(int j = SZ(vec[i]) - 1; j; j -= j & -j)
		{
			ret += F[Tp][i][j];
		}
		for(int j = id - 1; j; j -= j & -j)
		{
			ret -= F[Tp][i][j];
		}
	}
	return ret;
}
 
inline void _add(int l, int r, int t)
{
	add(l, r, 0, -t);
	add(l, r, 1, 1);
}
 
inline void _del(int l, int r, int t)
{
	add(l, r, 0, t);
	add(l, r, 1, -1);
}
 
void ins(int i, int t)
{
	if(st.empty()) { st.insert(Mp(i, i)); _add(i, i, t); return; }
	auto it = st.lower_bound(Mp(i, 0));
	if(it == st.end())
	{
		it --; pii cu = *it;
		if(cu.S == i - 1) { st.erase(it); _del(cu.F, cu.S, t); cu.S ++; st.insert(cu); _add(cu.F, cu.S, t); }
		else st.insert(Mp(i, i)), _add(i, i, t);
		return;
	}
	pii R = *it;
	if(it == st.begin())
	{
		if(R.F == i + 1) { st.erase(R); _del(R.F, R.S, t); R.F --; st.insert(R); _add(R.F, R.S, t); }
		else st.insert(Mp(i, i)), _add(i, i, t);
		return;
	}
	auto it2 = it; it2 --; pii L = *it2;
	if(L.S + 1 == R.F - 1) { st.erase(L); _del(L.F, L.S, t); st.erase(R); _del(R.F, R.S, t); st.insert(Mp(L.F, R.S)); _add(L.F, R.S, t); }
	else if(L.S + 1 == i) { st.erase(L); _del(L.F, L.S, t); st.insert(Mp(L.F, i)); _add(L.F, i, t); }
	else if(R.F == i + 1) { st.erase(R); _del(R.F, R.S, t); st.insert(Mp(i, R.S)); _add(i, R.S, t); }
	else st.insert(Mp(i, i)), _add(i, i, t);
 
}
 
void del(int i, int t)
{
	auto it = st.upper_bound(Mp(i, mod));
	it --;
	pii cu = *it;
	_del(cu.F, cu.S, t);
	st.erase(cu);
	if(cu.F < i && i < cu.S)
	{
		st.insert(Mp(cu.F, i - 1)); _add(cu.F, i - 1, t);
		st.insert(Mp(i + 1, cu.S)); _add(i + 1, cu.S, t);
	}
	else if(cu.F == i && i < cu.S) st.insert(Mp(i + 1, cu.S)), _add(i + 1, cu.S, t);
	else if(cu.F < i && cu.S == i) st.insert(Mp(cu.F, i - 1)), _add(cu.F, i - 1, t);
 
}
 
int main()
{
	scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
	string t = s;
	set < pii > goshad;
	int last = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(s[i] == '0')
		{
			if(last == i - 1) { last = i; continue; }
			pre_add(last + 1, i - 1); st.insert(Mp(last + 1, i - 1)); goshad.insert(Mp(last + 1, i - 1));
			last = i;
		}
	}
	if(last != n) { pre_add(last + 1, n); st.insert(Mp(last + 1, n)); goshad.insert(Mp(last + 1, n)); }	
	for(int i = 1; i <= q; i ++)
	{
		scanf("%s%d", C, &fir[i]);
		if(C[0] == 't') tp[i] = 1;
		else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
		if(tp[i] == 1)
		{
			if(s[fir[i]] == '0') pre_ins(fir[i]), s[fir[i]] = '1';
			else pre_del(fir[i]), s[fir[i]] = '0';
		}
		else
		{
			pre_add(fir[i], sec[i]);
		}
	}
	prep();
	st = goshad;
	for(auto x : st)
	{
		_add(x.F, x.S, 0);
	}
	s = t;
	for(int i = 1; i <= q; i ++)
	{
		if(tp[i] == 1)
		{
			if(s[fir[i]] == '0')
			{
				s[fir[i]] = '1';
				ins(fir[i], i);
			}
			else
			{
				s[fir[i]] = '0';
				del(fir[i], i);
			}
		}
		else
		{
			ll tot = 1ll * i * get(fir[i], sec[i], 1) + get(fir[i], sec[i], 0);
			printf("%lld\n", tot);
		}
	}
    return 0;
}
 
/** tesy corney cases(n = 1?) watch for overflow or minus indices **/

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  178 |  scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  194 |   scanf("%s%d", C, &fir[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:196:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |   else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
      |                   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 70764 KB Output is correct
2 Correct 48 ms 70764 KB Output is correct
3 Correct 48 ms 70764 KB Output is correct
4 Correct 48 ms 70764 KB Output is correct
5 Correct 54 ms 70764 KB Output is correct
6 Correct 54 ms 70892 KB Output is correct
7 Correct 48 ms 70764 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 86224 KB Output is correct
2 Correct 466 ms 87640 KB Output is correct
3 Correct 831 ms 94936 KB Output is correct
4 Correct 2947 ms 197004 KB Output is correct
5 Correct 2806 ms 197172 KB Output is correct
6 Correct 2956 ms 195656 KB Output is correct
7 Correct 1380 ms 176696 KB Output is correct
8 Correct 1391 ms 178088 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 71020 KB Output is correct
2 Correct 50 ms 71184 KB Output is correct
3 Correct 51 ms 71148 KB Output is correct
4 Correct 51 ms 71148 KB Output is correct
5 Correct 3491 ms 182924 KB Output is correct
6 Correct 3549 ms 200220 KB Output is correct
7 Correct 3156 ms 212188 KB Output is correct
8 Correct 2160 ms 200712 KB Output is correct
9 Correct 254 ms 86980 KB Output is correct
10 Correct 267 ms 88400 KB Output is correct
11 Correct 295 ms 90836 KB Output is correct
12 Correct 2123 ms 199340 KB Output is correct
13 Correct 2135 ms 200876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 71148 KB Output is correct
2 Correct 51 ms 71192 KB Output is correct
3 Correct 51 ms 71148 KB Output is correct
4 Correct 50 ms 71148 KB Output is correct
5 Correct 2594 ms 218100 KB Output is correct
6 Correct 2803 ms 210864 KB Output is correct
7 Correct 3171 ms 203308 KB Output is correct
8 Correct 3793 ms 192688 KB Output is correct
9 Correct 578 ms 88272 KB Output is correct
10 Correct 445 ms 83920 KB Output is correct
11 Correct 580 ms 88404 KB Output is correct
12 Correct 450 ms 83920 KB Output is correct
13 Correct 579 ms 88404 KB Output is correct
14 Correct 452 ms 84056 KB Output is correct
15 Correct 2112 ms 193452 KB Output is correct
16 Correct 2178 ms 194808 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 70764 KB Output is correct
2 Correct 48 ms 70764 KB Output is correct
3 Correct 48 ms 70764 KB Output is correct
4 Correct 48 ms 70764 KB Output is correct
5 Correct 54 ms 70764 KB Output is correct
6 Correct 54 ms 70892 KB Output is correct
7 Correct 48 ms 70764 KB Output is correct
8 Correct 376 ms 86224 KB Output is correct
9 Correct 466 ms 87640 KB Output is correct
10 Correct 831 ms 94936 KB Output is correct
11 Correct 2947 ms 197004 KB Output is correct
12 Correct 2806 ms 197172 KB Output is correct
13 Correct 2956 ms 195656 KB Output is correct
14 Correct 1380 ms 176696 KB Output is correct
15 Correct 1391 ms 178088 KB Output is correct
16 Correct 50 ms 71020 KB Output is correct
17 Correct 50 ms 71184 KB Output is correct
18 Correct 51 ms 71148 KB Output is correct
19 Correct 51 ms 71148 KB Output is correct
20 Correct 3491 ms 182924 KB Output is correct
21 Correct 3549 ms 200220 KB Output is correct
22 Correct 3156 ms 212188 KB Output is correct
23 Correct 2160 ms 200712 KB Output is correct
24 Correct 254 ms 86980 KB Output is correct
25 Correct 267 ms 88400 KB Output is correct
26 Correct 295 ms 90836 KB Output is correct
27 Correct 2123 ms 199340 KB Output is correct
28 Correct 2135 ms 200876 KB Output is correct
29 Correct 49 ms 71148 KB Output is correct
30 Correct 51 ms 71192 KB Output is correct
31 Correct 51 ms 71148 KB Output is correct
32 Correct 50 ms 71148 KB Output is correct
33 Correct 2594 ms 218100 KB Output is correct
34 Correct 2803 ms 210864 KB Output is correct
35 Correct 3171 ms 203308 KB Output is correct
36 Correct 3793 ms 192688 KB Output is correct
37 Correct 578 ms 88272 KB Output is correct
38 Correct 445 ms 83920 KB Output is correct
39 Correct 580 ms 88404 KB Output is correct
40 Correct 450 ms 83920 KB Output is correct
41 Correct 579 ms 88404 KB Output is correct
42 Correct 452 ms 84056 KB Output is correct
43 Correct 2112 ms 193452 KB Output is correct
44 Correct 2178 ms 194808 KB Output is correct
45 Correct 180 ms 80596 KB Output is correct
46 Correct 294 ms 83412 KB Output is correct
47 Correct 1726 ms 135380 KB Output is correct
48 Correct 3311 ms 211312 KB Output is correct
49 Correct 297 ms 90188 KB Output is correct
50 Correct 297 ms 90840 KB Output is correct
51 Correct 316 ms 92616 KB Output is correct
52 Correct 377 ms 95452 KB Output is correct
53 Correct 376 ms 95304 KB Output is correct
54 Correct 376 ms 95428 KB Output is correct