oj.uz

Submission #1036466

# Submission time Handle Problem Language Result Execution time Memory
1036466 2024-07-27T11:58:40 Z baojiaopisu Fish 3 (JOI24_fish3) C++14
27 / 100
 936 ms 80468 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, A5K37 Le Quy Don High School for Gifted Student, Da Nang */

/*       University of Wollongong       */

const ll INF = 1e9;
const int N = 3e5 + 10;

struct SegTree {
	int n;
	bool dbg = false;
	struct Node {
		ll lazy = 0;
		ll s = 0;
		ll val = INF * INF;
		ll sum = 0;
		ll cnt = 0;

		Node() {
			sum = 0;
			lazy = s = cnt = 0;
			val = INF * INF;
		}
	};
	vector<Node> node;

	SegTree(int _n = 0) {
		n = _n;
		node.resize(4 * n + 7);
		for(int i = 1; i <= 4 * n; i++) {
			node[i] = Node();
			node[i].val = 0;
		}
	}
private:
	void Down(int l, int r, int id) {
		ll x = node[id].lazy;
		node[id << 1].lazy += x;
		node[id << 1 | 1].lazy += x;
		node[id << 1].val += x;
		node[id << 1 | 1].val += x;
		int mid = (l + r) >> 1;
		node[id << 1].s += x * (mid - l + 1);
		node[id << 1 | 1].s += x * (r - mid);
		node[id << 1].sum += x * (mid - l + 1);
		node[id << 1 | 1].sum += x * (r - mid);
		node[id].lazy = 0;
	}

	pll walk(int l, int r, ll val, int id) {
		if(node[id].val >= val) {
			return {node[id].s, r - l + 1};
		}

		if(l == r) return {0, 0};

		Down(l, r, id);
		int mid = (l + r) >> 1;
		pll curr = walk(mid + 1, r, val, id << 1 | 1);
		if(curr.se == (r - mid)) {
			pll nxt = walk(l, mid, val, id << 1);
			return {curr.fi + nxt.fi, curr.se + nxt.se};
		} else return curr;
	}

	Node merge(const Node &a, const Node &b, int l, int r, int id) {
		Node ans = Node();
		if(a.val == INF * INF) return b;
		if(b.val == INF * INF) return a;
		int mid = (l + r) >> 1;
		if(a.val >= b.val) {
			ans.s = b.s + b.val * a.cnt;
		} else {
			pll curr = walk(l, mid, b.val, id << 1);
			ans.s = b.s + a.s - curr.fi + curr.se * b.val;
		}
		ans.sum = a.sum + b.sum;
		ans.cnt = a.cnt + b.cnt;
		ans.val = min(a.val, b.val);
		return ans;
	}

	void Update(int l, int r, int lo, int hi, ll val, int id) {
		if(l > hi || r < lo) return;
		if(lo <= l && r <= hi) {
			if(l == r) node[id].cnt = 1;
			node[id].s += val * (r - l + 1);
			node[id].val += val;
			node[id].lazy += val;
			node[id].sum += val * (r - l + 1);
			return;
		}

		Down(l, r, id);
		int mid = (l + r) >> 1;
		Update(l, mid, lo, hi, val, id << 1);
		Update(mid + 1, r, lo, hi, val, id << 1 | 1);
		node[id] = merge(node[id << 1], node[id << 1 | 1], l, r, id);
	}

	Node Get(int l, int r, int lo, int hi, int id) {
		if(l > hi || r < lo) return Node();
		if(lo <= l && r <= hi) return node[id];

		Down(l, r, id);
		int mid = (l + r) >> 1;
		Node left = Get(l, mid, lo, hi, id << 1);
		Node right = Get(mid + 1, r, lo, hi, id << 1 | 1);
		return merge(left, right, l, r, id);
	}
public:
	void update(int l, int r, ll val) {
		Update(1, n, l, r, val, 1);
	}

	pll get(int l, int r) {
		Node ans = Get(1, n, l, r, 1);
		return {ans.val, ans.sum - ans.s};
	}
};

ll a[N], b[N], ans[N], pref[N], t[N];
vector<pii> query[N];

void BaoJiaoPisu() {
	int n; ll d; cin >> n >> d;
	SegTree IT = SegTree(n);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		IT.update(i, i, a[i]);
	}


	for(int i = 2; i <= n; i++) {
		b[i] = ((a[i] % d) + d - (a[i - 1] % d)) % d;  
		IT.update(i, n, -b[i]);
	}	

	int q; cin >> q;	
	for(int i = 1; i <= q; i++) {
		int l, r; cin >> l >> r;
		query[l].pb({r, i});
	}

	for(int i = 1; i <= n; i++) {
		IT.update(i, n, b[i]);	

		IT.update(i, n, -(a[i] % d));
		for(auto [r, id] : query[i]) {
			pll curr = IT.get(i, r);
			if(curr.fi < 0) {
				ans[id] = -1;
			} else {
				ans[id] = (IT.get(i, r).se) / d;
			}
		}
		IT.update(i, n, a[i] % d);
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        BaoJiaoPisu();
    }
}

Compilation message

Main.cpp: In function 'void BaoJiaoPisu()':
Main.cpp:214:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  214 |   for(auto [r, id] : query[i]) {
      |            ^
Main.cpp: In function 'int main()':
Main.cpp:231:17: warning: unused variable 'ddd' [-Wunused-variable]
  231 |     int tc = 1, ddd = 0;
      |                 ^~~

Subtask #1
0 / 9.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 73732 KB Output is correct
2 Correct 936 ms 72960 KB Output is correct
3 Correct 130 ms 17744 KB Output is correct
4 Correct 627 ms 72788 KB Output is correct
5 Correct 647 ms 72712 KB Output is correct
6 Correct 725 ms 72456 KB Output is correct
7 Correct 781 ms 72528 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 21592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 64608 KB Output is correct
2 Correct 830 ms 73764 KB Output is correct
3 Correct 413 ms 31572 KB Output is correct
4 Correct 910 ms 76980 KB Output is correct
5 Correct 770 ms 73300 KB Output is correct
6 Correct 842 ms 80212 KB Output is correct
7 Correct 697 ms 68000 KB Output is correct
8 Correct 805 ms 80468 KB Output is correct
9 Correct 661 ms 73040 KB Output is correct
10 Correct 673 ms 72788 KB Output is correct
11 Correct 779 ms 76984 KB Output is correct
12 Correct 735 ms 76272 KB Output is correct
13 Correct 779 ms 80012 KB Output is correct
14 Correct 709 ms 75928 KB Output is correct
15 Correct 800 ms 80028 KB Output is correct
16 Correct 693 ms 75856 KB Output is correct

Subtask #5
0 / 36.0

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