oj.uz

Submission #379543

# Submission time Handle Problem Language Result Execution time Memory
379543 2021-03-18T13:55:09 Z AriaH Street Lamps (APIO19_street_lamps) C++11
60 / 100
 3581 ms 157156 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 < int > 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]) + 1, 0);
		F[1][i].resize(SZ(vec[i]) + 1, 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();
		if(checking)
		{	printf("i = %d id = %d\n", i, id);
			printf("vec : \n");
			for(auto x : vec[i]) printf("%d ", x);
			printf("done\n");
		}
		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)); }	
	/*printf("checking\n");
	for(auto x : st)
	{
		printf("%d %d  ", x.F, x.S);
	}
	printf("\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]);
		}
		/*printf("i = %d\n", i);
		for(auto x : st) printf("%d %d  ", x.F, x.S);
		printf("\n");*/
	}
	prep();
	st = goshad;
	for(auto x : st)
	{
		///printf("adding : %d %d\n", x.F, x.S);
		_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
		{
			/*checking = 1;
			get(fir[i], sec[i], 1);
			checking = 0;*/
			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:184:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  184 |  scanf("%d%d%s", &n, &q, C); s = C; s = "." + s;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  206 |   scanf("%s%d", C, &fir[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:208:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  208 |   else tp[i] = 2, scanf("%d", &sec[i]), sec[i] --;
      |                   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70764 KB Output is correct
2 Correct 49 ms 70764 KB Output is correct
3 Correct 54 ms 70764 KB Output is correct
4 Correct 48 ms 70764 KB Output is correct
5 Correct 48 ms 71020 KB Output is correct
6 Correct 48 ms 70764 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 367 ms 84064 KB Output is correct
2 Correct 465 ms 85212 KB Output is correct
3 Correct 771 ms 89132 KB Output is correct
4 Correct 2709 ms 146180 KB Output is correct
5 Correct 2607 ms 147004 KB Output is correct
6 Correct 2799 ms 145080 KB Output is correct
7 Correct 1369 ms 134332 KB Output is correct
8 Correct 1373 ms 135820 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 71020 KB Output is correct
2 Correct 50 ms 71020 KB Output is correct
3 Correct 50 ms 71020 KB Output is correct
4 Correct 49 ms 71020 KB Output is correct
5 Correct 3307 ms 137020 KB Output is correct
6 Incorrect 3318 ms 147488 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 71020 KB Output is correct
2 Correct 51 ms 71020 KB Output is correct
3 Correct 57 ms 71148 KB Output is correct
4 Correct 53 ms 71148 KB Output is correct
5 Correct 2409 ms 157156 KB Output is correct
6 Correct 2595 ms 152776 KB Output is correct
7 Correct 2969 ms 148288 KB Output is correct
8 Correct 3581 ms 142464 KB Output is correct
9 Correct 571 ms 84436 KB Output is correct
10 Correct 440 ms 81496 KB Output is correct
11 Correct 573 ms 84436 KB Output is correct
12 Correct 443 ms 81624 KB Output is correct
13 Correct 569 ms 84444 KB Output is correct
14 Correct 450 ms 81628 KB Output is correct
15 Correct 1985 ms 142156 KB Output is correct
16 Correct 1996 ms 143460 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70764 KB Output is correct
2 Correct 49 ms 70764 KB Output is correct
3 Correct 54 ms 70764 KB Output is correct
4 Correct 48 ms 70764 KB Output is correct
5 Correct 48 ms 71020 KB Output is correct
6 Correct 48 ms 70764 KB Output is correct
7 Correct 48 ms 70764 KB Output is correct
8 Correct 367 ms 84064 KB Output is correct
9 Correct 465 ms 85212 KB Output is correct
10 Correct 771 ms 89132 KB Output is correct
11 Correct 2709 ms 146180 KB Output is correct
12 Correct 2607 ms 147004 KB Output is correct
13 Correct 2799 ms 145080 KB Output is correct
14 Correct 1369 ms 134332 KB Output is correct
15 Correct 1373 ms 135820 KB Output is correct
16 Correct 51 ms 71020 KB Output is correct
17 Correct 50 ms 71020 KB Output is correct
18 Correct 50 ms 71020 KB Output is correct
19 Correct 49 ms 71020 KB Output is correct
20 Correct 3307 ms 137020 KB Output is correct
21 Incorrect 3318 ms 147488 KB Output isn't correct
22 Halted 0 ms 0 KB -