oj.uz

답안 #623677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623677 2022-08-06T09:15:54 Z MateGiorbelidze 자리 배치 (IOI18_seats) C++14
17 / 100
 4000 ms 48692 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

std::vector<int> r , c , mxr, mxc, mnr, mnc;

int ans = 0 , h , w;


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r = R; c = C; h = H; w = W;
  
  mxr.resize( h * w + 1 );
  mxc.resize( h * w + 1 );
  mnr.resize( h * w + 1 );
  mnc.resize( h * w + 1 );
  
  mxr[0] = mxc[0] = INT_MIN;
  mnr[0] = mnc[0] = INT_MAX;
  
  for (int i = 1; i <= h * w; i++) {
  	
      mxr[i] = max(mxr[i - 1] , r[i - 1]);
      mxc[i] = max(mxc[i - 1] , c[i - 1]);
      mnr[i] = min(mnr[i - 1] , r[i - 1]);
      mnc[i] = min(mnc[i - 1] , c[i - 1]);
      
      if ( (mxr[i] - mnr[i] + 1) * (mxc[i] - mnc[i] + 1) == i) ans++;
  }
  
}

int swap_seats(int a, int b) {
	a++; b++;
	if (a > b) swap(a , b);
	
	 for (int i = a; i <= b; i++) 
      if ( (mxr[i] - mnr[i] + 1) * (mxc[i] - mnc[i] + 1) == i) ans--;
    
	swap (r[a - 1] , r[b - 1]);
	swap (c[a - 1] , c[b - 1]);  
      
    for (int i = a; i <= b; i++) {
  	
      mxr[i] = max(mxr[i - 1] , r[i - 1]);
      mxc[i] = max(mxc[i - 1] , c[i - 1]);
      mnr[i] = min(mnr[i - 1] , r[i - 1]);
      mnc[i] = min(mnc[i - 1] , c[i - 1]);
      
      if ( (mxr[i] - mnr[i] + 1) * (mxc[i] - mnc[i] + 1) == i) ans++;
  }  
  
	
  return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 436 KB Output is correct
12 Correct 4 ms 436 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 436 KB Output is correct
12 Correct 4 ms 436 KB Output is correct
13 Correct 90 ms 892 KB Output is correct
14 Correct 101 ms 888 KB Output is correct
15 Correct 88 ms 896 KB Output is correct
16 Correct 101 ms 884 KB Output is correct
17 Correct 91 ms 884 KB Output is correct
18 Correct 89 ms 888 KB Output is correct
19 Correct 107 ms 884 KB Output is correct
20 Correct 92 ms 900 KB Output is correct
21 Correct 92 ms 900 KB Output is correct
22 Correct 101 ms 888 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4061 ms 39972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 852 KB Output is correct
2 Correct 310 ms 5084 KB Output is correct
3 Correct 530 ms 46052 KB Output is correct
4 Correct 555 ms 46256 KB Output is correct
5 Correct 565 ms 48544 KB Output is correct
6 Correct 538 ms 48688 KB Output is correct
7 Correct 559 ms 48620 KB Output is correct
8 Correct 541 ms 48692 KB Output is correct
9 Correct 535 ms 48588 KB Output is correct
10 Correct 540 ms 48644 KB Output is correct
11 Correct 539 ms 48692 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1480 KB Output is correct
2 Correct 19 ms 1948 KB Output is correct
3 Correct 31 ms 1888 KB Output is correct
4 Correct 103 ms 2048 KB Output is correct
5 Correct 855 ms 2516 KB Output is correct
6 Execution timed out 4027 ms 39960 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 436 KB Output is correct
12 Correct 4 ms 436 KB Output is correct
13 Correct 90 ms 892 KB Output is correct
14 Correct 101 ms 888 KB Output is correct
15 Correct 88 ms 896 KB Output is correct
16 Correct 101 ms 884 KB Output is correct
17 Correct 91 ms 884 KB Output is correct
18 Correct 89 ms 888 KB Output is correct
19 Correct 107 ms 884 KB Output is correct
20 Correct 92 ms 900 KB Output is correct
21 Correct 92 ms 900 KB Output is correct
22 Correct 101 ms 888 KB Output is correct
23 Execution timed out 4061 ms 39972 KB Time limit exceeded
24 Halted 0 ms 0 KB -