oj.uz

답안 #260970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260970 2020-08-11T08:55:19 Z 송준혁(#5049) 청소 (JOI20_sweeping) C++17
10 / 100
 1795 ms 2097156 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int L, N, M, Q;
int S[1505050], Q1[1010101], Q2[1010101];
int X[1505050], Y[1505050], A[1010101];
vector<int> T[4040404];

void build(int id, int s, int e){
	if (s == e){
		T[id].pb(A[s]);
		return;
	}
	int m=s+e>>1;
	build(id*2, s, m), build(id*2+1, m+1, e);
	for (int x : T[id*2]) T[id].pb(x);
	for (int x : T[id*2+1]) T[id].pb(x);
	inplace_merge(T[id].begin(), T[id].begin()+T[id*2].size(), T[id].end());
}

int query(int id, int s, int e, int ts, int te, int k){
	if (e < ts || te < s) return 0;
	if (ts <= s && e <= te){
		auto it = lower_bound(T[id].begin(), T[id].end(), k);
		if (it == T[id].end()) return 0;
		return L - *it;
	}
	int m=s+e>>1;
	return max(query(id*2, s, m, ts, te, k), query(id*2+1, m+1, e, ts, te, k));
}

int main(){
	scanf("%d %d %d", &L, &N, &Q);
	for (int i=1; i<=N; i++) scanf("%d %d", &X[i], &Y[i]);
	for (int i=1; i<=Q; i++){
		int x, y;
		scanf("%d", &x);
		if (x == 1){
			scanf("%d", &Q1[i]);
			Q2[i] = M;
		}
		else if (x == 2){
			M++;
			scanf("%d", &A[M]);
			Q2[i] = M;
		}
		else{
			N++;
			scanf("%d %d", &X[N], &Y[N]);
			S[N] = M;
		}
	}
	build(1, 1, M);
	for (int i=1; i<=Q; i++){
		if (Q1[i] == 0) continue;
		printf("%d %d\n", max(X[Q1[i]], query(1, 1, M, S[Q1[i]]+1, Q2[i], Y[Q1[i]])), Y[Q1[i]]);
	}
	return 0;
}

Compilation message

sweeping.cpp: In function 'void build(int, int, int)':
sweeping.cpp:25:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=s+e>>1;
        ~^~
sweeping.cpp: In function 'int query(int, int, int, int, int, int)':
sweeping.cpp:39:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=s+e>>1;
        ~^~
sweeping.cpp: In function 'int main()':
sweeping.cpp:47:10: warning: unused variable 'y' [-Wunused-variable]
   int x, y;
          ^
sweeping.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &L, &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:45:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%d %d", &X[i], &Y[i]);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
sweeping.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &Q1[i]);
    ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &A[M]);
    ~~~~~^~~~~~~~~~~~~
sweeping.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &X[N], &Y[N]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1115 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1724 ms 177160 KB Output is correct
2 Correct 1711 ms 177192 KB Output is correct
3 Correct 1681 ms 176992 KB Output is correct
4 Correct 1457 ms 183612 KB Output is correct
5 Correct 1432 ms 176756 KB Output is correct
6 Correct 1159 ms 174624 KB Output is correct
7 Correct 1795 ms 176980 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1442 ms 183336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1442 ms 183336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1115 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -