oj.uz

Submission #1065424

# Submission time Handle Problem Language Result Execution time Memory
1065424 2024-08-19T07:29:03 Z 김은성(#11116) Food Court (JOI21_foodcourt) C++17
2 / 100
 10 ms 23900 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 3.1557e18;
ll mn[1<<19], mn2[1<<19];
ll crit[1<<19], reset[1<<19], add[1<<19];
void mergenode(int v){
	if(mn[2*v] < mn[2*v+1]){
		mn[v] = mn[2*v];
		mn2[v] = min(mn2[2*v], mn[2*v+1]);
	}
	else if(mn[2*v] > mn[2*v+1]){
		mn[v] = mn[2*v+1];
		mn2[v] = min(mn2[2*v+1], mn[2*v]);
	}
	else{
		mn[v] = mn[2*v];
		mn2[v] = min(mn2[2*v], mn2[2*v+1]);
	}
}
void dolazy(int v, bool op){
	//assert(mn[v] < mn2[v]);
	if(mn[v] == crit[v])
		mn[v] = reset[v];
	else
		mn[v] += add[v];
	mn2[v] += add[v];
	if(!op){
		if(reset[2*v] == crit[v])
			reset[2*v] = reset[v];
		else
			reset[2*v] += add[v];
		add[2*v] += add[v];
		if(reset[2*v+1] == crit[v])
			reset[2*v+1] = reset[v];
		else
			reset[2*v+1] += add[v];
		add[2*v+1] += add[v];
	}
	crit[v] = INF;
	add[v] = 0;
}
void update(int v, int l, int r, int s, int e, ll d){
	dolazy(v, l==r);
	if(e<l || r<s)
		return;
	if(s<=l && r<=e){
		if(l==r){
			mn[v] = max(mn[v] + d, 0ll);
			mn2[v] = INF;
			return;
		}
		else if(mn[v] > -d){
			mn[v] += d;
			mn2[v] += d;
			add[2*v] += d;
			add[2*v+1] += d;
			return;
		}
		/*
		else if(mn2[v] > -d){
			crit[2*v] = mn[v];
			reset[2*v] = 0;
			add[2*v] += d;
			crit[2*v+1] = mn[v];
			reset[2*v+1] = 0;
			add[2*v+1] += d;
			mn[v] = 0;
			mn2[v] += d;
			return;
		}*/
	}
	int mid = (l+r)/2;
	update(2*v, l, mid, s, e, d);
	update(2*v+1, mid+1, r, s, e, d);
	mergenode(v);
}
ll pointvalue(int v, int l, int r, int idx){
	dolazy(v, l==r);
	if(l==r)
		return mn[v];
	int mid = (l+r)/2;
	if(idx <= mid)
		return pointvalue(2*v, l, mid, idx);
	return pointvalue(2*v+1, mid+1, r, idx);
}
int main(){
	int n, m, q, i, t, type, l, r, c, a;
	ll k, b;
	scanf("%d %d %d", &n, &m, &q);
	assert(n<=2000 && q<=2000);
	//assert(m==1);
	memset(mn2, 63, sizeof(mn2));
	memset(crit, 63, sizeof(crit));
	deque<int> qa[(const int)(n+1)];
	for(t=1; t<=q; t++){
		scanf("%d", &type);
		if(type==1){
			scanf("%d %d %d %lld", &l, &r, &c, &k);
			for(i=l; i<=r; i++)
				qa[i].push_back(c);
			update(1, 1, n, l, r, k);
		}
		else if(type==2){
			scanf("%d %d %lld", &l, &r, &k);
			for(i=l; i<=r; i++){
				if(!qa[i].empty())
					qa[i].pop_front();
			}
			update(1, 1, n, l, r, -k);
		}
		else{
			scanf("%d %lld", &a, &b);
			if(pointvalue(1, 1, n, a) >= b){
				printf("%d\n", qa[a][b-1]);
			}
			else
				printf("0\n");
		}
	}
	return 0;
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d", &type);
      |   ~~~~~^~~~~~~~~~~~~
foodcourt.cpp:99:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |    scanf("%d %d %d %lld", &l, &r, &c, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d %d %lld", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:113:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    scanf("%d %lld", &a, &b);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11868 KB Output is correct
2 Correct 6 ms 12300 KB Output is correct
3 Correct 6 ms 13676 KB Output is correct
4 Correct 8 ms 14680 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 8 ms 14684 KB Output is correct
8 Correct 7 ms 14172 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 8 ms 13916 KB Output is correct
11 Correct 7 ms 13404 KB Output is correct
12 Correct 8 ms 12380 KB Output is correct
13 Correct 9 ms 12888 KB Output is correct
14 Correct 9 ms 13148 KB Output is correct
15 Correct 7 ms 12848 KB Output is correct
16 Correct 10 ms 12892 KB Output is correct
17 Correct 5 ms 11612 KB Output is correct
18 Correct 7 ms 12188 KB Output is correct
19 Correct 3 ms 11612 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11868 KB Output is correct
2 Correct 6 ms 12300 KB Output is correct
3 Correct 6 ms 13676 KB Output is correct
4 Correct 8 ms 14680 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 8 ms 14684 KB Output is correct
8 Correct 7 ms 14172 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 8 ms 13916 KB Output is correct
11 Correct 7 ms 13404 KB Output is correct
12 Correct 8 ms 12380 KB Output is correct
13 Correct 9 ms 12888 KB Output is correct
14 Correct 9 ms 13148 KB Output is correct
15 Correct 7 ms 12848 KB Output is correct
16 Correct 10 ms 12892 KB Output is correct
17 Correct 5 ms 11612 KB Output is correct
18 Correct 7 ms 12188 KB Output is correct
19 Correct 3 ms 11612 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Runtime error 9 ms 23900 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11868 KB Output is correct
2 Correct 6 ms 12300 KB Output is correct
3 Correct 6 ms 13676 KB Output is correct
4 Correct 8 ms 14680 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 8 ms 14684 KB Output is correct
8 Correct 7 ms 14172 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 8 ms 13916 KB Output is correct
11 Correct 7 ms 13404 KB Output is correct
12 Correct 8 ms 12380 KB Output is correct
13 Correct 9 ms 12888 KB Output is correct
14 Correct 9 ms 13148 KB Output is correct
15 Correct 7 ms 12848 KB Output is correct
16 Correct 10 ms 12892 KB Output is correct
17 Correct 5 ms 11612 KB Output is correct
18 Correct 7 ms 12188 KB Output is correct
19 Correct 3 ms 11612 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Runtime error 1 ms 348 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11868 KB Output is correct
2 Correct 6 ms 12300 KB Output is correct
3 Correct 6 ms 13676 KB Output is correct
4 Correct 8 ms 14680 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 8 ms 14684 KB Output is correct
8 Correct 7 ms 14172 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 8 ms 13916 KB Output is correct
11 Correct 7 ms 13404 KB Output is correct
12 Correct 8 ms 12380 KB Output is correct
13 Correct 9 ms 12888 KB Output is correct
14 Correct 9 ms 13148 KB Output is correct
15 Correct 7 ms 12848 KB Output is correct
16 Correct 10 ms 12892 KB Output is correct
17 Correct 5 ms 11612 KB Output is correct
18 Correct 7 ms 12188 KB Output is correct
19 Correct 3 ms 11612 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Runtime error 9 ms 23900 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11868 KB Output is correct
2 Correct 6 ms 12300 KB Output is correct
3 Correct 6 ms 13676 KB Output is correct
4 Correct 8 ms 14680 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 8 ms 14684 KB Output is correct
8 Correct 7 ms 14172 KB Output is correct
9 Correct 8 ms 12380 KB Output is correct
10 Correct 8 ms 13916 KB Output is correct
11 Correct 7 ms 13404 KB Output is correct
12 Correct 8 ms 12380 KB Output is correct
13 Correct 9 ms 12888 KB Output is correct
14 Correct 9 ms 13148 KB Output is correct
15 Correct 7 ms 12848 KB Output is correct
16 Correct 10 ms 12892 KB Output is correct
17 Correct 5 ms 11612 KB Output is correct
18 Correct 7 ms 12188 KB Output is correct
19 Correct 3 ms 11612 KB Output is correct
20 Correct 3 ms 11868 KB Output is correct
21 Runtime error 9 ms 23900 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -