oj.uz

답안 #124735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124735 2019-07-03T20:06:07 Z dragonslayerit 자리 배치 (IOI18_seats) C++14
5 / 100
 4000 ms 75732 KB 
#include "seats.h"
#include <tuple>
#include <algorithm>
#include <iostream>

static const int INF=1e9+7;

struct Node{
  int max[4];
}st[2000000];
int N,H,W;

std::vector<std::tuple<int,int,int> > rectangles;

void pull(int i){
  for(int k=0;k<4;k++){
    st[i].max[k]=std::max(st[i<<1].max[k],st[i<<1|1].max[k]);
  }
}

void build(int i){
  for(i+=N;i>1;i>>=1){
    pull(i>>1);
  }
}

int query(int k,int b){
  int a=0;
  int res=-INF;
  for(a+=N,b+=N;a<b;a>>=1,b>>=1){
    if(a&1) res=std::max(res,st[a++].max[k]);
    if(b&1) res=std::max(res,st[--b].max[k]);
  }
  return res;
}

void give_initial_chart(int h, int w, std::vector<int> R, std::vector<int> C) {
  H=h;
  W=w;
  N=h*w;
  for(int i=0;i<N;i++){
    st[i+N].max[0]=R[i];
    st[i+N].max[1]=-R[i];
    st[i+N].max[2]=C[i];
    st[i+N].max[3]=-C[i];
  }
  for(int i=N-1;i>0;i--){
    pull(i);
  }
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      rectangles.emplace_back(i*j,i,j);
    }
  }
  std::sort(rectangles.begin(),rectangles.end());
}

int swap_seats(int a, int b) {
  for(int k=0;k<4;k++){
    std::swap(st[a+N].max[k],st[b+N].max[k]);
  }
  build(a),build(b);
  int cnt=0;
  for(auto rect:rectangles){
    int area=std::get<0>(rect);
    int h=std::get<1>(rect);
    int w=std::get<2>(rect);
    if(query(0,area)+query(1,area)==h-1&&
       query(2,area)+query(3,area)==w-1){
      //std::cerr<<"RECT: "<<h<<"x"<<w<<std::endl;
      cnt++;
    }
  }
  return cnt;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 16 ms 464 KB Output is correct
4 Correct 30 ms 476 KB Output is correct
5 Correct 35 ms 496 KB Output is correct
6 Correct 25 ms 488 KB Output is correct
7 Correct 19 ms 632 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 18 ms 504 KB Output is correct
10 Correct 16 ms 504 KB Output is correct
11 Correct 17 ms 504 KB Output is correct
12 Correct 30 ms 496 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 16 ms 464 KB Output is correct
4 Correct 30 ms 476 KB Output is correct
5 Correct 35 ms 496 KB Output is correct
6 Correct 25 ms 488 KB Output is correct
7 Correct 19 ms 632 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 18 ms 504 KB Output is correct
10 Correct 16 ms 504 KB Output is correct
11 Correct 17 ms 504 KB Output is correct
12 Correct 30 ms 496 KB Output is correct
13 Correct 3990 ms 1336 KB Output is correct
14 Correct 3982 ms 1336 KB Output is correct
15 Execution timed out 4088 ms 1336 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2036 KB Output is correct
2 Correct 37 ms 2064 KB Output is correct
3 Correct 278 ms 2072 KB Output is correct
4 Execution timed out 4033 ms 1700 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 16 ms 464 KB Output is correct
4 Correct 30 ms 476 KB Output is correct
5 Correct 35 ms 496 KB Output is correct
6 Correct 25 ms 488 KB Output is correct
7 Correct 19 ms 632 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 18 ms 504 KB Output is correct
10 Correct 16 ms 504 KB Output is correct
11 Correct 17 ms 504 KB Output is correct
12 Correct 30 ms 496 KB Output is correct
13 Correct 3990 ms 1336 KB Output is correct
14 Correct 3982 ms 1336 KB Output is correct
15 Execution timed out 4088 ms 1336 KB Time limit exceeded
16 Halted 0 ms 0 KB -