oj.uz

답안 #869617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869617 2023-11-05T04:14:36 Z abhidot Meteors (POI11_met) C++17
74 / 100
 598 ms 40968 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mod 1000000007
#define mod2 998244353
#define lld long double
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define V vector
#define setbits(x) __builtin_popcountll(x)
#define w(x)  int x; cin>>x; while(x--)
using namespace std;
using namespace __gnu_pbds; 
template <typename num_t> using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
const long long N=300005, INF=2000000000000000000, inf = 2e9+5;
 
int power(int a, int b, int p){
	if(a==0)
	return 0;
	int res=1;
	a%=p;
	while(b>0)
	{
		if(b&1)
		res=(res*a)%p;
		b>>=1;
		a=(a*a)%p;
	}
	return res;
}
 
 
void print(bool n){
    if(n){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

int n, m, q, till=0;
vector<int> owners, reqd, ans; 
vector<vector<int>> queries, inc;

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            update(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void update(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

FenwickTree bit(N);

void apply(int l, int r, int a){
	if(l<=r){
		bit.update(l, a);
		bit.update(r+1, -a);
	}else{
		bit.update(l, a);
		bit.update(m, -a);
		bit.update(0, a);
		bit.update(r+1, -a);
	}
}

void update(int idx){
	while(till<idx){
		till++;
		// cout<<q<<" "<<till<<": ";
		// for(int i: queries[till]) cout<<i<<" "; cout<<"\n";
		apply(queries[till][0], queries[till][1], queries[till][2]);
	}
	while(till>idx){
		apply(queries[till][0], queries[till][1], -queries[till][2]);
		till--;
	}
}

void rec(int l, int r, vector<int>& states){
	if(l==r){
		for(int i:states) ans[i]=l;
		states.clear();
		return;
	}
	int mid = (l+r)/2;
	update(mid);
	int sm=0;
	vector<int> L, R;
	for(int i:states){
		int have=0;
		for(int j:inc[i]){
			have+=bit.sum(j);
		}
		if(have>=reqd[i]) L.pb(i);
		else R.pb(i);
	}
	states.clear();
	rec(l, mid, L);
	rec(mid+1, r, R);
}
 
int32_t main()
{
    IOS;
		cin>>n>>m;
		owners.resize(m);
		reqd.resize(n);
		ans.resize(n, -1);
		inc.resize(n);
		for(int i=0;i<m;i++){
			cin>>owners[i];
			owners[i]--;
			inc[owners[i]].pb(i);
		}
		for(int i=0;i<n;i++){
			cin>>reqd[i];
		}
		
		cin>>q;
		queries.resize(q+2);
		queries[0]={0,0,0};
		queries[q+1]={0,0,0};
		for(int i=1;i<=q;i++){
			int l, r, a;
			cin>>l>>r>>a;
			--l, --r;
			queries[i]={l, r, a};
		}
		
		vector<int> states;
		for(int i=0;i<n;i++) states.pb(i);
		rec(0, q+1, states);
		
		for(int i=0;i<n;i++){
			if(ans[i]==q+1){
				cout<<"NIE\n";
			}else cout<<ans[i]<<"\n";
		}
}

Compilation message

met.cpp: In function 'void rec(long long int, long long int, std::vector<long long int>&)':
met.cpp:123:6: warning: unused variable 'sm' [-Wunused-variable]
  123 |  int sm=0;
      |      ^~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3064 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 7404 KB Output is correct
2 Correct 97 ms 10976 KB Output is correct
3 Correct 61 ms 7560 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 7492 KB Output is correct
2 Correct 78 ms 7256 KB Output is correct
3 Correct 94 ms 9728 KB Output is correct
4 Correct 19 ms 5720 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 7208 KB Output is correct
2 Correct 86 ms 10188 KB Output is correct
3 Correct 62 ms 5588 KB Output is correct
4 Correct 60 ms 7888 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 6356 KB Output is correct
2 Correct 95 ms 7288 KB Output is correct
3 Correct 47 ms 6736 KB Output is correct
4 Correct 85 ms 9172 KB Output is correct

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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