oj.uz

Submission #437564

# Submission time Handle Problem Language Result Execution time Memory
437564 2021-06-26T14:22:24 Z RohamIzadidoost Street Lamps (APIO19_street_lamps) C++14
60 / 100
 4503 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+50 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
ll n , q ; 
string c ; 
set<ll> s ; 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<ll, 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&-l ) for(int i = r ; i ; i -= i&-i ) 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 88 ms 91856 KB Output is correct
2 Correct 90 ms 91844 KB Output is correct
3 Correct 94 ms 91964 KB Output is correct
4 Correct 92 ms 91972 KB Output is correct
5 Correct 95 ms 92040 KB Output is correct
6 Correct 95 ms 92012 KB Output is correct
7 Correct 94 ms 91788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2285 ms 93144 KB Output is correct
2 Correct 2016 ms 93712 KB Output is correct
3 Correct 1980 ms 104680 KB Output is correct
4 Correct 3695 ms 382648 KB Output is correct
5 Correct 3802 ms 392828 KB Output is correct
6 Correct 3973 ms 396832 KB Output is correct
7 Correct 1258 ms 106956 KB Output is correct
8 Correct 747 ms 94284 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 116 ms 93536 KB Output is correct
3 Correct 99 ms 93268 KB Output is correct
4 Correct 94 ms 91844 KB Output is correct
5 Runtime error 4503 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 89 ms 91956 KB Output is correct
2 Correct 99 ms 93216 KB Output is correct
3 Correct 101 ms 93348 KB Output is correct
4 Correct 107 ms 93532 KB Output is correct
5 Correct 2132 ms 116780 KB Output is correct
6 Correct 3609 ms 344324 KB Output is correct
7 Correct 4237 ms 396600 KB Output is correct
8 Correct 4385 ms 434092 KB Output is correct
9 Correct 2529 ms 93224 KB Output is correct
10 Correct 4395 ms 92292 KB Output is correct
11 Correct 2637 ms 93216 KB Output is correct
12 Correct 4111 ms 92316 KB Output is correct
13 Correct 2618 ms 93116 KB Output is correct
14 Correct 4170 ms 92312 KB Output is correct
15 Correct 1495 ms 106828 KB Output is correct
16 Correct 737 ms 94324 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 91856 KB Output is correct
2 Correct 90 ms 91844 KB Output is correct
3 Correct 94 ms 91964 KB Output is correct
4 Correct 92 ms 91972 KB Output is correct
5 Correct 95 ms 92040 KB Output is correct
6 Correct 95 ms 92012 KB Output is correct
7 Correct 94 ms 91788 KB Output is correct
8 Correct 2285 ms 93144 KB Output is correct
9 Correct 2016 ms 93712 KB Output is correct
10 Correct 1980 ms 104680 KB Output is correct
11 Correct 3695 ms 382648 KB Output is correct
12 Correct 3802 ms 392828 KB Output is correct
13 Correct 3973 ms 396832 KB Output is correct
14 Correct 1258 ms 106956 KB Output is correct
15 Correct 747 ms 94284 KB Output is correct
16 Correct 105 ms 93880 KB Output is correct
17 Correct 116 ms 93536 KB Output is correct
18 Correct 99 ms 93268 KB Output is correct
19 Correct 94 ms 91844 KB Output is correct
20 Runtime error 4503 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -