oj.uz

Submission #191491

# Submission time Handle Problem Language Result Execution time Memory
191491 2020-01-15T02:27:35 Z dndhk Sushi (JOI16_sushi) C++14
15 / 100
 1535 ms 10720 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 400000;
const int SQ = 700;

int N, Q;
int arr[MAX_N+1];
int g[MAX_N+1];
priority_queue<int> pq1[SQ+1], pq2;

int solve(int gn, int s, int e, int k){
	int x = gn*SQ+1, y = min((gn+1)*SQ, N);
	//cout<<s<<" "<<e<<" "<<k<<" "<<endl;
	//cout<<x<<" "<<y<<endl;
	if(s<=x && y<=e){
		pq1[gn].push(k);
		k = pq1[gn].top();
		pq1[gn].pop();
		return k;
	}else{
		while(!pq2.empty())	pq2.pop();
		for(int i=y; i>=x; i--){
			while(!pq1[gn].empty() && !pq2.empty() && pq1[gn].top()==pq2.top()){
				pq1[gn].pop();
				pq2.pop();
			}
			//cout<<i<<" "<<pq1[gn].top()<<" "<<arr[i]<<endl;
			if(arr[i]>pq1[gn].top()){
				arr[i] = pq1[gn].top();
				pq1[gn].pop();
			}else{
				pq2.push(arr[i]);
			}
		}
		for(int i=x; i<=y; i++){
			if(s<=i && i<=e){
				if(k<arr[i]){
					int tmp = k;
					k = arr[i];
					arr[i] = tmp;
				}
			}
			pq1[gn].push(arr[i]);
		}
		return k;
	}
}

int main(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++){
		scanf("%d", &arr[i]);
		g[i] = (i-1)/SQ;
		pq1[g[i]].push(arr[i]);
	}
	for(int i=1; i<=Q; i++){
		int s, e, k;
		scanf("%d%d%d", &s, &e, &k);
		if(s<=e){
			int n = g[s];
			while(n<=g[e]){
				k = solve(n, s, e, k);
				n++;
			}
		}else{
			int n = g[s];
			while(n<=g[N]){
				k = solve(n, s, N, k);
				n++;
			}
			n = 0;
			while(n<=g[e]){
				k = solve(n, 1, e, k);
				n++;
			}
		}
		printf("%d\n", k);
	}

}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &s, &e, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 10532 KB Output is correct
2 Correct 1528 ms 9212 KB Output is correct
3 Correct 984 ms 7128 KB Output is correct
4 Correct 1519 ms 10444 KB Output is correct
5 Correct 865 ms 10516 KB Output is correct
6 Correct 1364 ms 10656 KB Output is correct
7 Correct 1363 ms 10648 KB Output is correct
8 Correct 1326 ms 10476 KB Output is correct
9 Correct 745 ms 7048 KB Output is correct
10 Correct 923 ms 8972 KB Output is correct
11 Correct 778 ms 7104 KB Output is correct
12 Correct 992 ms 9320 KB Output is correct
13 Correct 1521 ms 10332 KB Output is correct
14 Correct 1514 ms 9188 KB Output is correct
15 Correct 961 ms 7032 KB Output is correct
16 Correct 1529 ms 10476 KB Output is correct
17 Correct 879 ms 10300 KB Output is correct
18 Correct 1356 ms 10592 KB Output is correct
19 Correct 1365 ms 10548 KB Output is correct
20 Correct 1349 ms 10720 KB Output is correct

Subtask #3
0 / 80.0

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