QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#377151#149. PerultunjicCompile Error//C++142.3kb2024-04-04 23:18:212024-09-10 16:45:52

Judging History

This is the latest submission verdict.

  • [2024-09-10 16:45:52]
  • 管理员手动重测本题所有提交记录
  • [2024-04-04 23:18:21]
  • Judged
  • [2024-04-04 23:18:21]
  • Submitted

answer

#include <cstdio> 
#include <deque> 
#include <queue> 
#include <stack> 

using namespace std;

typedef long long ll;

const int N = 3e6 + 10; 
const int MOD = 1e9 + 7;
const ll OO = 1e18;

int add(int a, int b) {
	if(a + b < MOD) return a + b;
	return a + b - MOD;
}

int mult(int a, int b) {
	return (ll) a * b % MOD;
}

struct bit {
	ll val, ind, mx; 
	bit(ll val, ll ind, ll mx) : val(val), ind(ind), mx(mx) {}

	bool operator < (bit x) { return val < x.val; }
	bool operator == (bit x) { return val == x.val && ind == x.ind && mx == x.mx; }
};

struct monotog {
	deque<bit> D; 
	bool empty() { return D.empty(); }
	ll get() { return D.empty() ? OO : D.back().val; }
	void push(bit x) { 
		if(get() >= x.val) D.push_back(x); 
		else D.push_back(D.back()); 
	}
	void pop() { D.pop_back(); }
	void clear() { for(; !D.empty(); pop()); }
}; 

struct monodeq { 
	monotog L, R; 
	deque<bit> D; 
	bool empty() { return D.empty(); }
	ll get() { return min(L.get(), R.get()); }
	void reload() {
		L.clear(); 
		R.clear(); 
		int siz = (int) D.size() / 2;
		for(int i = siz; i < D.size(); ++i) R.push(D[i]); 
		for(int i = siz - 1; i >= 0; --i) L.push(D[i]); 
	}
	void push_front(bit x) { L.push(x); D.push_front(x); }
	void push_back(bit x) { R.push(x); D.push_back(x); }
	void pop_front() {
		D.pop_front();
		if(L.empty()) reload();
		else L.pop(); 
	}
	void pop_back() {
		D.pop_back(); 
		if(R.empty()) reload(); 
		else R.pop();
	}
	bit front() { return D.front(); }
};

int n, k; 
ll DP[N]; 

deque<bit> Q;
monodeq D;

int main() {
	scanf("%d%d", &n, &k); 
	for(int i = 1; i <= n; ++i) {
		int x; scanf("%d", &x);
		int ind = i - 1;
		for(; !Q.empty() && Q.back().mx < x; Q.pop_back()) {
			ind = Q.back().ind;
			D.pop_back();
		}

		Q.push_back(bit(DP[ind] + x, ind, x));
		D.push_back(Q.back());
		
//		printf("%lld\n", D.get());
		if(i > k) {
			bit lst = D.front(); 
			Q.pop_front(); 
			D.pop_front(); 
			if(D.empty() || lst.ind + 1 != D.front().ind) {
				Q.push_front(bit(DP[lst.ind + 1] + lst.mx, lst.ind + 1, lst.mx));
				D.push_front(Q.front());
			}
		}

		DP[i] = D.get();
//		printf("%d %lld\n", i, DP[i]);
	}

	int ans = 0, p = 1;
	for(int i = n; i >= 1; --i) {
		ans = add(ans, mult(DP[i] % MOD, p));
		p = mult(p, 23);
	}
	printf("%d\n", ans);
	return 0;
}

Details

implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:77:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   77 |         scanf("%d%d", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
answer.code:79:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |                 int x; scanf("%d", &x);
      |                        ~~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccuz5oj0.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccV4bIqZ.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccV4bIqZ.o: in function `main':
implementer.cpp:(.text.startup+0x151): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status