oj.uz

Submission #437558

# Submission time Handle Problem Language Result Execution time Memory
437558 2021-06-26T14:07:18 Z RohamIzadidoost Street Lamps (APIO19_street_lamps) C++17
60 / 100
 4448 ms 524292 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ld long double
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 3000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int n , q ; 
string c ; 
set<int> s ; 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, ll> fen[maxn];
ll res ;  
inline void add(int l , int r , ll x){
	for( ; l < maxn ; l += l & -l ) for(int i = r ; i < maxn ; i += i & -i ) fen[l][i] += x ; 
}
inline void get(int l , int r){
	res = 0 ; 
	for( ; l ; l &= l-1 ) for(int i = r ; i ; i &= i-1) if(fen[l].find(i) != fen[l].end()) res += fen[l][i] ; 
}
void doj(int l , int r , int l2 , int r2 , ll x){
	add(l , r , x) ; 
	add(l2 + 1 , r2 + 1 , x) ; 
	add(l , r2 + 1 , -x) ; 
	add(l2 + 1 , r , -x) ; 
}
int main()
{
	migmig ;
	/*for(int i = 1 ; i < maxn ; i ++ ){
		fen[i].max_load_factor(0.13); 
	}*/
	cin>>n>>q>>c ; 
	s.insert(0) ;
	s.insert(n + 1) ;  
	for(int i = 0 ; i < n ; i ++ ){
		if(c[i] == '0') s.insert(i + 1) ; 
	}
	ll l , r ;
	ll v ;  
	for(ll i = 1 ; i <= q ; i ++ ){
		cin>>c ; 
		if(c == "query"){
			cin>>l>>r ; 
			get(l , r) ; 
			//cout<<*s.lower_bound(l) << endl ; 
			if(s.lower_bound(l) == s.lower_bound(r) ) res += i ; 
			cout<<res << "\n" ; 
			continue ; 	
		}
		cin>>v ; 
		auto p = s.lower_bound(v) ; 
		if(*p == v){
			l = *prev(p) + 1 ; 
			r = *next(p) ; 
			s.erase(v) ; 
			doj(l , v + 1 , v , r , -i ) ;
		//	cout<<l <<","<< r << endl ; 
			continue ;  
		}
		l = *prev(p) + 1 ; 
		r = *p ; 
	//	cout<<l<<" " << r << endl ; 
		s.insert(v) ; 
		doj(l , v + 1 , v , r , i) ; 
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 91844 KB Output is correct
2 Correct 84 ms 91836 KB Output is correct
3 Correct 82 ms 91884 KB Output is correct
4 Correct 106 ms 92008 KB Output is correct
5 Correct 140 ms 91964 KB Output is correct
6 Correct 103 ms 91768 KB Output is correct
7 Correct 87 ms 91844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2325 ms 93108 KB Output is correct
2 Correct 1947 ms 93624 KB Output is correct
3 Correct 1986 ms 104460 KB Output is correct
4 Correct 3911 ms 382864 KB Output is correct
5 Correct 3849 ms 393112 KB Output is correct
6 Correct 4202 ms 397156 KB Output is correct
7 Correct 1402 ms 107532 KB Output is correct
8 Correct 788 ms 94784 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 93880 KB Output is correct
2 Correct 94 ms 93516 KB Output is correct
3 Correct 103 ms 93280 KB Output is correct
4 Correct 136 ms 91816 KB Output is correct
5 Runtime error 4378 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 92032 KB Output is correct
2 Correct 98 ms 93164 KB Output is correct
3 Correct 111 ms 93400 KB Output is correct
4 Correct 119 ms 93584 KB Output is correct
5 Correct 2058 ms 116980 KB Output is correct
6 Correct 3590 ms 344428 KB Output is correct
7 Correct 4448 ms 396596 KB Output is correct
8 Correct 4306 ms 433956 KB Output is correct
9 Correct 2522 ms 93064 KB Output is correct
10 Correct 4038 ms 92280 KB Output is correct
11 Correct 2670 ms 93752 KB Output is correct
12 Correct 4045 ms 92972 KB Output is correct
13 Correct 2544 ms 93732 KB Output is correct
14 Correct 4054 ms 92848 KB Output is correct
15 Correct 1397 ms 107480 KB Output is correct
16 Correct 739 ms 94936 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 91844 KB Output is correct
2 Correct 84 ms 91836 KB Output is correct
3 Correct 82 ms 91884 KB Output is correct
4 Correct 106 ms 92008 KB Output is correct
5 Correct 140 ms 91964 KB Output is correct
6 Correct 103 ms 91768 KB Output is correct
7 Correct 87 ms 91844 KB Output is correct
8 Correct 2325 ms 93108 KB Output is correct
9 Correct 1947 ms 93624 KB Output is correct
10 Correct 1986 ms 104460 KB Output is correct
11 Correct 3911 ms 382864 KB Output is correct
12 Correct 3849 ms 393112 KB Output is correct
13 Correct 4202 ms 397156 KB Output is correct
14 Correct 1402 ms 107532 KB Output is correct
15 Correct 788 ms 94784 KB Output is correct
16 Correct 105 ms 93880 KB Output is correct
17 Correct 94 ms 93516 KB Output is correct
18 Correct 103 ms 93280 KB Output is correct
19 Correct 136 ms 91816 KB Output is correct
20 Runtime error 4378 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -