oj.uz

답안 #741540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741540 2023-05-14T10:11:40 Z shadow_sami 가로등 (APIO19_street_lamps) C++17
20 / 100
 242 ms 27664 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 3e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
bool a[mx];
ll q;
string k;
ll start[mx];

typedef struct SEGMENT_TREE{
	vi arr;
	ll range;
	void init(ll a){
		range = log2(a);
		range = 1 << (range + 3);
		arr.resize(range);
		return;
	}
	ll construct(ll ptr,ll l,ll r){
		if(l==r){
			arr[ptr] = start[l];
			return arr[ptr];
		}
		ll mid = l + (r-l) / 2;
		arr[ptr] = max(construct(2*ptr,l,mid),construct(2*ptr+1,mid+1,r));
		return arr[ptr];
	}
	ll query(ll ptr,ll l,ll r,ll st,ll en){
		if(l > en || r < st)
			return 0;
		if(l>=st && r<=en)
			return arr[ptr];
		ll mid = l + (r-l)/2;
		return max(query(2*ptr,l,mid,st,en),query(2*ptr+1,mid+1,r,st,en));
	}
	ll update(ll ptr,ll l,ll r,ll val,ll pos){
		if(l==r && r==pos){
			start[l] = val;
			arr[ptr] = val;
			return arr[ptr];
		}
		if(l > pos || r < pos)
			return arr[ptr];
		ll mid = l + (r-l)/2;
		arr[ptr] = max(update(2*ptr,l,mid,val,pos),update(2*ptr+1,mid+1,r,val,pos));
		return arr[ptr];
	}
	void debugg(ll ptr,ll l,ll r){
		cout<<ptr<<" "<<l<<" "<<r<<""<< " "<<arr[ptr]<<nli;
		if(l==r)
			return;
		ll mid = l + (r-l)/2;
		debugg(2*ptr,l,mid);
		debugg(2*ptr+1,mid+1,r);
	}
}SGT;

SGT sgt;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>q;
        cin>>k;
        fip(0,n)
        	a[i] = (k[i]=='1') ? 1 : 0;
        ll sr,de;
        fip(0,n)
        	start[i] = (k[i]=='1') ? 0 : 1e9;        
        sgt.init(n);
        sgt.construct(1,0,n-1);
        // sgt.debugg(1,0,n-1);
        // fip(0,n)
        // 	cout<<sgt.query(1,0,n-1,i,i)<<nli;
        fip(1,q+1){
        	cin>>k;
        	if(k == "query"){
        		cin>>sr>>de;
        		sr--,de--;
        		tp = sgt.query(1,0,n-1,sr,de-1);
        		// cout<<tp<<" "<<i<<nli;
        		if(tp>i)
        			cout<<0<<nli;
        		else
        			cout<<i-tp<<nli;
        	}
        	else{
        		// mark[i] = 1;
        		cin>>sr;
        		sr--;
        		a[sr] = 1;
        		sgt.update(1,0,n-1,i,sr);
        	}
        }
        // fip(0,n)
        // 	cout<<total[i]<<" ";
        // cout<<nli;
        // fip(0,n)
        // 	cout<<start[i]<<" ";
        // cout<<nli;
        // cout<<"ok";

        
    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 3068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 148 ms 24012 KB Output is correct
6 Correct 191 ms 24740 KB Output is correct
7 Correct 230 ms 25420 KB Output is correct
8 Correct 224 ms 27664 KB Output is correct
9 Correct 87 ms 3980 KB Output is correct
10 Correct 88 ms 4232 KB Output is correct
11 Correct 95 ms 4452 KB Output is correct
12 Correct 224 ms 26224 KB Output is correct
13 Correct 242 ms 27664 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -