oj.uz

답안 #437547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437547 2021-06-26T13:53:31 Z RohamIzadidoost 가로등 (APIO19_street_lamps) C++14
20 / 100
 4718 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 ; 
unordered_map<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) ; 
	}
	int 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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 16716 KB Output is correct
2 Correct 15 ms 16844 KB Output is correct
3 Correct 16 ms 16852 KB Output is correct
4 Correct 17 ms 16972 KB Output is correct
5 Correct 16 ms 16936 KB Output is correct
6 Correct 18 ms 16704 KB Output is correct
7 Correct 17 ms 16716 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2507 ms 18248 KB Output is correct
2 Correct 2638 ms 19580 KB Output is correct
3 Correct 3257 ms 38136 KB Output is correct
4 Runtime error 4718 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 20668 KB Output is correct
2 Correct 32 ms 19564 KB Output is correct
3 Correct 26 ms 18844 KB Output is correct
4 Correct 16 ms 16716 KB Output is correct
5 Runtime error 3063 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 16844 KB Output is correct
2 Correct 23 ms 18636 KB Output is correct
3 Correct 29 ms 19212 KB Output is correct
4 Correct 36 ms 19456 KB Output is correct
5 Correct 1529 ms 54744 KB Output is correct
6 Correct 4223 ms 445776 KB Output is correct
7 Runtime error 3636 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 16716 KB Output is correct
2 Correct 15 ms 16844 KB Output is correct
3 Correct 16 ms 16852 KB Output is correct
4 Correct 17 ms 16972 KB Output is correct
5 Correct 16 ms 16936 KB Output is correct
6 Correct 18 ms 16704 KB Output is correct
7 Correct 17 ms 16716 KB Output is correct
8 Correct 2507 ms 18248 KB Output is correct
9 Correct 2638 ms 19580 KB Output is correct
10 Correct 3257 ms 38136 KB Output is correct
11 Runtime error 4718 ms 524292 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -