oj.uz

Submission #437557

# Submission time Handle Problem Language Result Execution time Memory
437557 2021-06-26T14:06:59 Z RohamIzadidoost Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 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 87 ms 91808 KB Output is correct
2 Correct 89 ms 91872 KB Output is correct
3 Correct 88 ms 91844 KB Output is correct
4 Correct 90 ms 92024 KB Output is correct
5 Correct 88 ms 91984 KB Output is correct
6 Correct 87 ms 91868 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 2233 ms 93324 KB Output is correct
2 Correct 1903 ms 93576 KB Output is correct
3 Correct 1852 ms 104620 KB Output is correct
4 Correct 3737 ms 382528 KB Output is correct
5 Correct 3577 ms 392744 KB Output is correct
6 Correct 4119 ms 396836 KB Output is correct
7 Correct 1310 ms 106940 KB Output is correct
8 Correct 801 ms 94360 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 93808 KB Output is correct
2 Correct 93 ms 93488 KB Output is correct
3 Correct 91 ms 93324 KB Output is correct
4 Correct 92 ms 91844 KB Output is correct
5 Runtime error 4394 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 92008 KB Output is correct
2 Correct 97 ms 93104 KB Output is correct
3 Correct 97 ms 93316 KB Output is correct
4 Correct 109 ms 93512 KB Output is correct
5 Correct 1952 ms 116688 KB Output is correct
6 Correct 3978 ms 344236 KB Output is correct
7 Correct 4424 ms 397088 KB Output is correct
8 Correct 4965 ms 434616 KB Output is correct
9 Correct 4203 ms 93756 KB Output is correct
10 Execution timed out 5084 ms 92840 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 91808 KB Output is correct
2 Correct 89 ms 91872 KB Output is correct
3 Correct 88 ms 91844 KB Output is correct
4 Correct 90 ms 92024 KB Output is correct
5 Correct 88 ms 91984 KB Output is correct
6 Correct 87 ms 91868 KB Output is correct
7 Correct 87 ms 91844 KB Output is correct
8 Correct 2233 ms 93324 KB Output is correct
9 Correct 1903 ms 93576 KB Output is correct
10 Correct 1852 ms 104620 KB Output is correct
11 Correct 3737 ms 382528 KB Output is correct
12 Correct 3577 ms 392744 KB Output is correct
13 Correct 4119 ms 396836 KB Output is correct
14 Correct 1310 ms 106940 KB Output is correct
15 Correct 801 ms 94360 KB Output is correct
16 Correct 98 ms 93808 KB Output is correct
17 Correct 93 ms 93488 KB Output is correct
18 Correct 91 ms 93324 KB Output is correct
19 Correct 92 ms 91844 KB Output is correct
20 Runtime error 4394 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -