oj.uz

답안 #808291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
808291 2023-08-05T05:48:07 Z Supersonic 자리 배치 (IOI18_seats) C++14
17 / 100
 4000 ms 83684 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> g;int h,w;int n;
pair<ll,ll> cmi[1000001];pair<ll,ll> cmx[1000001];
int cl[1000001],cr[1000001],cu[1000001],cd[1000001];


struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    void add(int idx, int val) {
      for (++idx; idx < n; idx += idx & -idx)
          bit[idx] += val;
    }

    void range_add(int l, int r, int val) {
        add(l, val);
        add(r + 1, -val);
    }

    int point_query(int idx) {
        int ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }

};

FenwickTree tf(1000010);

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++){g.push_back({R[i],C[i]});}
  //tf=FenwickTree(1000001);
  /*tf.range_add(0,1000,5);
  tf.range_add(5,1000,5);
  cerr<<tf.point_query(2)<<' '<<tf.point_query(8)<<endl;*/
  //exit(1);


  pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001};
  int lm=1000001,um=1000001,rm=-1000001,dm=-1000001;
  long long t=0;
  for(int i=0;i<=n;i++){
    mi=min(mi,g[i]);mx=max(mx,g[i]);
    if(g[i].second<lm)lm=g[i].second;
    if(g[i].second>rm)rm=g[i].second;
    if(g[i].first<um)um=g[i].first;
    if(g[i].first>dm)dm=g[i].first;
    //cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second;
    if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl;
    cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm;
    
    int c=tf.point_query(i);
    tf.add(i,t-c);
  }



}

int swap_seats(int a, int b) {
  
  swap(g[a],g[b]);
  pair<ll,ll> mi,mx;mi={1000001,1000001};mx={-1000001,-1000001};
  int lm=1000001,um=1000001,rm=-1000001,dm=-1000001;
  long long t=0;
  if(a>b)swap(a,b);
  if(a>0&&b>0){int i=a-1;t=tf.point_query(i);mi=cmi[i];mx=cmx[i];lm=cl[i];rm=cr[i];um=cu[i];dm=cd[i];}
  int bb=-1;
  for(int i=a;i<=b;i++){
    mi=min(mi,g[i]);mx=max(mx,g[i]);
    if(g[i].second<lm)lm=g[i].second;
    if(g[i].second>rm)rm=g[i].second;
    if(g[i].first<um)um=g[i].first;
    if(g[i].first>dm)dm=g[i].first;
    //cerr<<mi.first<<' '<<mi.second<<" | "<<mx.first<<' '<<mx.second;
    if((mx.first-mi.first+1)*(mx.second-mi.second+1)==i+1&&rm-lm==mx.second-mi.second&&dm-um==mx.first-mi.first){t++;}//cerr<<" ***";}cerr<<endl;
    cmi[i]=mi;cmx[i]=mx;cl[i]=lm;cr[i]=rm;cu[i]=um;cd[i]=dm;
    
    int c=tf.point_query(i);
    tf.add(i,t-c);
    if(i==b)bb=t-c;
    //cerr<<lm<<'-'<<um<<'-'<<rm<<'-'<<dm<<endl;
    //cerr<<(lm-rm)<<' '<<mx.second-mi.second<<endl;
    //cerr<<(lm-rm==mx.second-mi.second)<<' '<<(dm-um==mx.first-mi.first)<<endl;
  }
  tf.range_add(b+1,n,bb);
  return tf.point_query(n-1);
}
/*
2 3 3
0 0
1 0
1 1
0 1
0 2
1 2
1 4
0 5
0 1

*/

/*

0 3 1
4 2 5

5 3 1
4 2 0

5 3 0
4 2 1
*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 6 ms 4456 KB Output is correct
3 Correct 10 ms 4412 KB Output is correct
4 Correct 10 ms 4380 KB Output is correct
5 Correct 10 ms 4372 KB Output is correct
6 Correct 10 ms 4436 KB Output is correct
7 Correct 11 ms 4436 KB Output is correct
8 Correct 9 ms 4420 KB Output is correct
9 Correct 9 ms 4436 KB Output is correct
10 Correct 12 ms 4436 KB Output is correct
11 Correct 10 ms 4436 KB Output is correct
12 Correct 10 ms 4376 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 6 ms 4456 KB Output is correct
3 Correct 10 ms 4412 KB Output is correct
4 Correct 10 ms 4380 KB Output is correct
5 Correct 10 ms 4372 KB Output is correct
6 Correct 10 ms 4436 KB Output is correct
7 Correct 11 ms 4436 KB Output is correct
8 Correct 9 ms 4420 KB Output is correct
9 Correct 9 ms 4436 KB Output is correct
10 Correct 12 ms 4436 KB Output is correct
11 Correct 10 ms 4436 KB Output is correct
12 Correct 10 ms 4376 KB Output is correct
13 Correct 497 ms 5332 KB Output is correct
14 Correct 537 ms 5336 KB Output is correct
15 Correct 571 ms 5328 KB Output is correct
16 Correct 514 ms 5344 KB Output is correct
17 Correct 523 ms 5328 KB Output is correct
18 Correct 508 ms 5344 KB Output is correct
19 Correct 508 ms 5348 KB Output is correct
20 Correct 493 ms 5328 KB Output is correct
21 Correct 502 ms 5328 KB Output is correct
22 Correct 502 ms 5332 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 772 ms 5224 KB Output is correct
2 Correct 737 ms 12076 KB Output is correct
3 Correct 883 ms 83440 KB Output is correct
4 Correct 888 ms 83684 KB Output is correct
5 Correct 917 ms 83532 KB Output is correct
6 Correct 862 ms 83640 KB Output is correct
7 Correct 950 ms 83660 KB Output is correct
8 Correct 859 ms 83564 KB Output is correct
9 Correct 870 ms 83668 KB Output is correct
10 Correct 869 ms 83572 KB Output is correct
11 Correct 930 ms 83588 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 5192 KB Output is correct
2 Correct 27 ms 5316 KB Output is correct
3 Correct 80 ms 5296 KB Output is correct
4 Correct 580 ms 5272 KB Output is correct
5 Execution timed out 4054 ms 5736 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 6 ms 4456 KB Output is correct
3 Correct 10 ms 4412 KB Output is correct
4 Correct 10 ms 4380 KB Output is correct
5 Correct 10 ms 4372 KB Output is correct
6 Correct 10 ms 4436 KB Output is correct
7 Correct 11 ms 4436 KB Output is correct
8 Correct 9 ms 4420 KB Output is correct
9 Correct 9 ms 4436 KB Output is correct
10 Correct 12 ms 4436 KB Output is correct
11 Correct 10 ms 4436 KB Output is correct
12 Correct 10 ms 4376 KB Output is correct
13 Correct 497 ms 5332 KB Output is correct
14 Correct 537 ms 5336 KB Output is correct
15 Correct 571 ms 5328 KB Output is correct
16 Correct 514 ms 5344 KB Output is correct
17 Correct 523 ms 5328 KB Output is correct
18 Correct 508 ms 5344 KB Output is correct
19 Correct 508 ms 5348 KB Output is correct
20 Correct 493 ms 5328 KB Output is correct
21 Correct 502 ms 5328 KB Output is correct
22 Correct 502 ms 5332 KB Output is correct
23 Execution timed out 4035 ms 82556 KB Time limit exceeded
24 Halted 0 ms 0 KB -