oj.uz

Submission #772817

# Submission time Handle Problem Language Result Execution time Memory
772817 2023-07-04T11:35:31 Z I_Love_EliskaM_ Seats (IOI18_seats) C++14
31 / 100
 4000 ms 60668 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9;

vector<int> r, c;
int n,m;

struct sgt {
  vector<pi> mn,mx; int sz=1;
  sgt(int n) {
    while (sz<n) sz<<=1;
    mn.assign(2*sz-1,{inf,inf});
    mx.assign(2*sz-1,{-inf,-inf});
  }
  void upd(int v, int l, int r, int i) {
    if (r-l==1) return;
    int m=(l+r)>>1;
    if (i<m) upd(2*v+1,l,m,i);
    else upd(2*v+2,m,r,i);
    mn[v].f=min(mn[2*v+1].f,mn[2*v+2].f);
    mn[v].s=min(mn[2*v+1].s,mn[2*v+2].s);
    mx[v].f=max(mx[2*v+1].f,mx[2*v+2].f);
    mx[v].s=max(mx[2*v+1].s,mx[2*v+2].s);
  }
  void set(int i, pi x) {
    mn[sz-1+i]=mx[sz-1+i]=x;
    upd(0,0,sz,i);
  }

  pair<pi,pi> query(int v, int l, int r, int lx, int rx) {
    if (rx<=l || r<=lx) return {{inf,inf},{-inf,-inf}};
    if (lx<=l && r<=rx) return {mn[v],mx[v]};
    int m=(l+r)>>1;
    auto lq = query(2*v+1,l,m,lx,rx);
    auto rq = query(2*v+2,m,r,lx,rx);
    return { {min(lq.f.f,rq.f.f),min(lq.f.s,rq.f.s)} , {max(lq.s.f,rq.s.f),max(lq.s.s,rq.s.s)} };
  }
  pair<pi,pi> query(int l, int r) {
    return query(0,0,sz,l,r);
  }
};
sgt st(1e6);

void give_initial_chart(int N, int M, vector<int> R, vector<int> C) {
  r=R, c=C;
  n=N, m=M;
  forn(i,n*m) st.set(i,{r[i],c[i]});
}

int swap_seats(int x, int y) {
  swap(r[x],r[y]);
  swap(c[x],c[y]);

  if (n*m<=1e4) {
      int ans=0;
      int lx=m-1, rx=0, u=n-1, d=0;
      forn(i,n*m) {
        lx=min(lx,c[i]), rx=max(rx,c[i]);
        u=min(u,r[i]), d=max(d,r[i]);
        ans += (rx-lx+1)*(d-u+1) == (i+1);
      }
      return ans;
  }

  st.set(x,{r[x],c[x]});
  st.set(y,{r[y],c[y]});

  int ans=0;
  int i=1;
  while (i<=n*m) {
    auto q = st.query(0,i);
    int u = q.f.f;
    int d = q.s.f;
    int l = q.f.s;
    int r = q.s.s;
    if ( (r-l+1)*(d-u+1) == i ) {
      ++ans;
      ++i;
    } else {
      i = (r-l+1)*(d-u+1);
    }
  }
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33236 KB Output is correct
2 Correct 15 ms 33300 KB Output is correct
3 Correct 15 ms 33244 KB Output is correct
4 Correct 15 ms 33236 KB Output is correct
5 Correct 15 ms 33236 KB Output is correct
6 Correct 15 ms 33236 KB Output is correct
7 Correct 15 ms 33324 KB Output is correct
8 Correct 15 ms 33276 KB Output is correct
9 Correct 15 ms 33236 KB Output is correct
10 Correct 15 ms 33236 KB Output is correct
11 Correct 15 ms 33356 KB Output is correct
12 Correct 15 ms 33236 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33236 KB Output is correct
2 Correct 15 ms 33300 KB Output is correct
3 Correct 15 ms 33244 KB Output is correct
4 Correct 15 ms 33236 KB Output is correct
5 Correct 15 ms 33236 KB Output is correct
6 Correct 15 ms 33236 KB Output is correct
7 Correct 15 ms 33324 KB Output is correct
8 Correct 15 ms 33276 KB Output is correct
9 Correct 15 ms 33236 KB Output is correct
10 Correct 15 ms 33236 KB Output is correct
11 Correct 15 ms 33356 KB Output is correct
12 Correct 15 ms 33236 KB Output is correct
13 Correct 160 ms 33600 KB Output is correct
14 Correct 144 ms 33580 KB Output is correct
15 Correct 140 ms 33612 KB Output is correct
16 Correct 153 ms 33576 KB Output is correct
17 Correct 132 ms 33576 KB Output is correct
18 Correct 147 ms 33580 KB Output is correct
19 Correct 133 ms 33576 KB Output is correct
20 Correct 137 ms 33584 KB Output is correct
21 Correct 134 ms 33588 KB Output is correct
22 Correct 144 ms 33588 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 60200 KB Output is correct
2 Correct 375 ms 60668 KB Output is correct
3 Correct 1953 ms 60176 KB Output is correct
4 Correct 411 ms 60116 KB Output is correct
5 Correct 380 ms 60100 KB Output is correct
6 Correct 2181 ms 60024 KB Output is correct
7 Correct 810 ms 60108 KB Output is correct
8 Correct 465 ms 60184 KB Output is correct
9 Correct 2109 ms 60164 KB Output is correct
10 Correct 1236 ms 60108 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33532 KB Output is correct
2 Correct 73 ms 36556 KB Output is correct
3 Correct 1814 ms 60148 KB Output is correct
4 Correct 371 ms 60188 KB Output is correct
5 Execution timed out 4054 ms 60156 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 34856 KB Output is correct
2 Correct 28 ms 34828 KB Output is correct
3 Correct 35 ms 34816 KB Output is correct
4 Correct 141 ms 34760 KB Output is correct
5 Correct 1236 ms 35064 KB Output is correct
6 Correct 1455 ms 60220 KB Output is correct
7 Correct 1191 ms 60144 KB Output is correct
8 Correct 1138 ms 60216 KB Output is correct
9 Correct 391 ms 60224 KB Output is correct
10 Execution timed out 4101 ms 60236 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33236 KB Output is correct
2 Correct 15 ms 33300 KB Output is correct
3 Correct 15 ms 33244 KB Output is correct
4 Correct 15 ms 33236 KB Output is correct
5 Correct 15 ms 33236 KB Output is correct
6 Correct 15 ms 33236 KB Output is correct
7 Correct 15 ms 33324 KB Output is correct
8 Correct 15 ms 33276 KB Output is correct
9 Correct 15 ms 33236 KB Output is correct
10 Correct 15 ms 33236 KB Output is correct
11 Correct 15 ms 33356 KB Output is correct
12 Correct 15 ms 33236 KB Output is correct
13 Correct 160 ms 33600 KB Output is correct
14 Correct 144 ms 33580 KB Output is correct
15 Correct 140 ms 33612 KB Output is correct
16 Correct 153 ms 33576 KB Output is correct
17 Correct 132 ms 33576 KB Output is correct
18 Correct 147 ms 33580 KB Output is correct
19 Correct 133 ms 33576 KB Output is correct
20 Correct 137 ms 33584 KB Output is correct
21 Correct 134 ms 33588 KB Output is correct
22 Correct 144 ms 33588 KB Output is correct
23 Correct 333 ms 60200 KB Output is correct
24 Correct 375 ms 60668 KB Output is correct
25 Correct 1953 ms 60176 KB Output is correct
26 Correct 411 ms 60116 KB Output is correct
27 Correct 380 ms 60100 KB Output is correct
28 Correct 2181 ms 60024 KB Output is correct
29 Correct 810 ms 60108 KB Output is correct
30 Correct 465 ms 60184 KB Output is correct
31 Correct 2109 ms 60164 KB Output is correct
32 Correct 1236 ms 60108 KB Output is correct
33 Correct 21 ms 33532 KB Output is correct
34 Correct 73 ms 36556 KB Output is correct
35 Correct 1814 ms 60148 KB Output is correct
36 Correct 371 ms 60188 KB Output is correct
37 Execution timed out 4054 ms 60156 KB Time limit exceeded
38 Halted 0 ms 0 KB -