oj.uz

답안 #437543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437543 2021-06-26T13:42:10 Z RohamIzadidoost 가로등 (APIO19_street_lamps) C++17
20 / 100
 5000 ms 254348 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 ;
	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 13 ms 16716 KB Output is correct
2 Correct 13 ms 16752 KB Output is correct
3 Correct 16 ms 16740 KB Output is correct
4 Correct 16 ms 16844 KB Output is correct
5 Correct 15 ms 16808 KB Output is correct
6 Correct 13 ms 16708 KB Output is correct
7 Correct 13 ms 16752 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3093 ms 17824 KB Output is correct
2 Correct 2744 ms 21820 KB Output is correct
3 Correct 3562 ms 28708 KB Output is correct
4 Execution timed out 5077 ms 205544 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 17996 KB Output is correct
2 Correct 28 ms 17852 KB Output is correct
3 Correct 23 ms 17484 KB Output is correct
4 Correct 15 ms 16716 KB Output is correct
5 Execution timed out 5066 ms 254348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 16848 KB Output is correct
2 Correct 22 ms 17484 KB Output is correct
3 Correct 27 ms 17732 KB Output is correct
4 Correct 35 ms 17952 KB Output is correct
5 Correct 1718 ms 41528 KB Output is correct
6 Execution timed out 5079 ms 177624 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 16716 KB Output is correct
2 Correct 13 ms 16752 KB Output is correct
3 Correct 16 ms 16740 KB Output is correct
4 Correct 16 ms 16844 KB Output is correct
5 Correct 15 ms 16808 KB Output is correct
6 Correct 13 ms 16708 KB Output is correct
7 Correct 13 ms 16752 KB Output is correct
8 Correct 3093 ms 17824 KB Output is correct
9 Correct 2744 ms 21820 KB Output is correct
10 Correct 3562 ms 28708 KB Output is correct
11 Execution timed out 5077 ms 205544 KB Time limit exceeded
12 Halted 0 ms 0 KB -