oj.uz

Submission #437563

# Submission time Handle Problem Language Result Execution time Memory
437563 2021-06-26T14:19:14 Z RohamIzadidoost Street Lamps (APIO19_street_lamps) C++17
60 / 100
 4895 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-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 104 ms 91844 KB Output is correct
2 Correct 96 ms 91896 KB Output is correct
3 Correct 110 ms 91852 KB Output is correct
4 Correct 96 ms 92088 KB Output is correct
5 Correct 91 ms 92056 KB Output is correct
6 Correct 96 ms 91900 KB Output is correct
7 Correct 105 ms 91844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2271 ms 93512 KB Output is correct
2 Correct 2053 ms 94180 KB Output is correct
3 Correct 2023 ms 104836 KB Output is correct
4 Correct 3740 ms 383124 KB Output is correct
5 Correct 3643 ms 392828 KB Output is correct
6 Correct 3903 ms 396708 KB Output is correct
7 Correct 1222 ms 106968 KB Output is correct
8 Correct 838 ms 94276 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 93892 KB Output is correct
2 Correct 106 ms 93616 KB Output is correct
3 Correct 123 ms 93312 KB Output is correct
4 Correct 100 ms 91800 KB Output is correct
5 Runtime error 4600 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 97 ms 92012 KB Output is correct
2 Correct 117 ms 93116 KB Output is correct
3 Correct 97 ms 93308 KB Output is correct
4 Correct 104 ms 93548 KB Output is correct
5 Correct 2156 ms 116748 KB Output is correct
6 Correct 3703 ms 344340 KB Output is correct
7 Correct 4207 ms 396588 KB Output is correct
8 Correct 4895 ms 434176 KB Output is correct
9 Correct 2720 ms 93132 KB Output is correct
10 Correct 4217 ms 92332 KB Output is correct
11 Correct 2659 ms 93040 KB Output is correct
12 Correct 4159 ms 92212 KB Output is correct
13 Correct 2710 ms 93124 KB Output is correct
14 Correct 4103 ms 92216 KB Output is correct
15 Correct 1441 ms 106828 KB Output is correct
16 Correct 722 ms 94412 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 91844 KB Output is correct
2 Correct 96 ms 91896 KB Output is correct
3 Correct 110 ms 91852 KB Output is correct
4 Correct 96 ms 92088 KB Output is correct
5 Correct 91 ms 92056 KB Output is correct
6 Correct 96 ms 91900 KB Output is correct
7 Correct 105 ms 91844 KB Output is correct
8 Correct 2271 ms 93512 KB Output is correct
9 Correct 2053 ms 94180 KB Output is correct
10 Correct 2023 ms 104836 KB Output is correct
11 Correct 3740 ms 383124 KB Output is correct
12 Correct 3643 ms 392828 KB Output is correct
13 Correct 3903 ms 396708 KB Output is correct
14 Correct 1222 ms 106968 KB Output is correct
15 Correct 838 ms 94276 KB Output is correct
16 Correct 103 ms 93892 KB Output is correct
17 Correct 106 ms 93616 KB Output is correct
18 Correct 123 ms 93312 KB Output is correct
19 Correct 100 ms 91800 KB Output is correct
20 Runtime error 4600 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -