oj.uz

Submission #996706

# Submission time Handle Problem Language Result Execution time Memory
996706 2024-06-11T06:13:25 Z SamuellH12 Fish 3 (JOI24_fish3) C++17
0 / 100
 2000 ms 64408 KB 
#include <bits/stdc++.h>
#define optimize ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ALL(x) x.begin(), x.end()
#define endl "\n"
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define INF 0x3f3f3f3f3f3f3f3f
const int MAXN = 3e5 + 5;
using namespace std;
#define int ll

const int MAXLG = 31 - __builtin_clz(MAXN) + 1;

vi fish;
int table[MAXN][MAXLG];

void calc(){
	int N = fish.size();
	for(int i=0; i<N; i++) table[i][0] = fish[i];

	for(int p=1; p < MAXLG; p++)
		for(int i=0; i + (1 << p) <= N; i++)
			table[i][p] = min(table[i][p-1], table[i+(1 << (p-1))][p-1]);
}

int queryst(int l, int r){
	int p = 31 - __builtin_clz(r - l + 1);	//floor log
	return min(table[l][p], table[ r - (1<<p) + 1 ][p]);
}

int bit[MAXN];

void update(int pos, int val){
	for(; pos < MAXN; pos += pos&(-pos))
		bit[pos] += val;
}

int query(int pos){
	int sum = 0;
	for(; pos > 0; pos -= pos&(-pos))
		sum += bit[pos];
	return sum;
}

int querypt(int pos){ return query(pos+1); } //+1 pq idx tá 0-index
void updateSeg(int l, int r, int val){ update(l+1, val), update(r+2, -val); }

const int BLOCK_SZ = 550;

struct Query{
	int l, r, idx;

	Query(int l, int r, int idx) : l(l), r(r), idx(idx) {}
	
	bool operator < (Query q) const {
		if(l / BLOCK_SZ != q.l / BLOCK_SZ) return l < q.l;
		return (l / BLOCK_SZ &1) ? ( r < q.r ) : (r > q.r );
	}
};


int D;
int minSufix = INF;
int A = 0;
int BACK = 0;
int L = 0, R = 0;

int lUpdate(int x, int RR){
	int ans = L;

	int l=L, r=RR, mid;
	while(l<=r)
	{
		mid = (l+r)/2;

		if(queryst(mid, RR) <= x) 
			ans = mid+1, l = mid+1;
		else r = mid-1;
	}

	return ans;
}

int getMinSufix(int l=L){ return fish[l] - querypt(l)*D; }

void add(int idx, bool sf){
	int C = fish[idx];

	if(sf && C < BACK) // sufixo //se C >= BACK não altera nada
	{
		int V = (BACK-C + D-1) / D;
		int l = lUpdate(C, R-1);
		
		if(l <= R-1) A += V*(R-l), updateSeg(l, R-1, V);  //(R-L+1 - 1) // -1 pq não conta com o C
	}
	else if(!sf) // prefixo
	{
		int V = max(C-getMinSufix(L+1) + D-1, 0LL) / D;	
		if(V) A += V, updateSeg(idx, idx, V);
	}

	BACK = fish[R];
}

void remove(int idx, bool sf){
	int C = fish[idx];
	BACK = fish[R];

	if(sf && C < BACK) // removendo C do sufixo
	{
		int V = (BACK-C + D-1) / D;
		int l = lUpdate(C-1, R);

		if(l<=R) A -= V*(R-l+1), updateSeg(l, R, -V);   //(R-L+1) //sem o -1 pq agora o intervalo já exclui o C
	}

	int V = querypt(idx);
	if(V) A -= V, updateSeg(idx, idx, -V);  // apaga o número da BIT
}

int getAnswer(){
	if(getMinSufix() >= 0LL) return A;
	else return -1LL;
}

void print(int l, int r){
	cerr << l << "L R" << r << endl;
	for(int i=0; i<fish.size(); i++) cerr << querypt(i) << " ";
	cerr << endl << endl;
}

vector<int> MO(vector<Query> &queries){
	vector<int> ans(queries.size());

	sort(queries.begin(), queries.end());

	L = 0, R = 0;
	add(0, true);

	for(auto [l, r, idx] : queries)
	{
		while(l < L) add(--L, false);
		// print(L, R);
		while(r > R) add(++R, true);
		// print(L, R);
		while(l > L) remove(L++, false);
		// print(L, R);
		while(r < R) remove(R--, true);
		// print(L, R);

		ans[idx] = getAnswer();
	}

	return ans;
}


int32_t main(){
	optimize;
	int n;
	cin >> n >> D;

	fish = vi(n);
	for(auto &x : fish) cin >> x;
	calc();

	int q;
	cin >> q;

	vector<Query> queries;

	for(int i=0, l, r; i<q; i++)
	{
		cin >> l >> r;
		l--, r--;
		queries.emplace_back(l, r, i);
	}

	auto ans = MO(queries);
	for(auto x : ans) cout << x << endl;
	
	return 0;	
}

Compilation message

Main.cpp: In function 'void print(long long int, long long int)':
Main.cpp:129:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for(int i=0; i<fish.size(); i++) cerr << querypt(i) << " ";
      |               ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 64408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 17780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 57920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -