oj.uz

Submission #454553

# Submission time Handle Problem Language Result Execution time Memory
454553 2021-08-05T05:51:33 Z ftkbrian Seats (IOI18_seats) C++14
5 / 100
 4000 ms 56780 KB 
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define pll pair<ll,ll>
#define f first
#define s second
vector<pll> X;
ll nm,inf = 1e9;
pll ST[2][4040404];
pll hp(pll a,pll b) { return {max(a.f,b.f),min(a.s,b.s)}; }
void upd(ll t,ll id,ll s,ll e,ll L,ll v) {
    if(s > L || L > e) return;
    if(s == e) { ST[t][id] = {v,v}; return; }
    ll m = s+e>>1;
    upd(t,id*2,s,m,L,v); upd(t,id*2+1,m+1,e,L,v);
    ST[t][id] = hp(ST[t][id*2],ST[t][id*2+1]);
}
pll hap(ll t,ll dx,ll s,ll e,ll qs,ll qe) {
    if(s > qe || e < qs) return {-inf,inf};
    if(qs <= s && e <= qe) return ST[t][dx];
    ll m = s+e>>1;
    return hp(hap(t,dx*2,s,m,qs,qe),hap(t,dx*2+1,m+1,e,qs,qe));
}
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
    for(int i = 0 ; i < r.size() ; i++) X.push_back({r[i],c[i]});
    nm = X.size();
    for(int i = 0 ; i < nm ; i++) {
        upd(0,1,0,nm-1,i,X[i].f);
        upd(1,1,0,nm-1,i,X[i].s);
    }
}

int swap_seats(int a, int b) {
    swap(X[a],X[b]);
    upd(0,1,0,nm-1,a,X[a].f);
    upd(0,1,0,nm-1,b,X[b].f);
    upd(1,1,0,nm-1,a,X[a].s);
    upd(1,1,0,nm-1,b,X[b].s);
    int s = 1,ret = 1;
    while(s < nm) {
        pll A = hap(0,1,0,nm-1,0,s);
        pll B = hap(1,1,0,nm-1,0,s);
        if((A.f-A.s+1)*(B.f-B.s+1) == s+1) ret++,s+=min(A.f-A.s+1,B.f-B.s+1);
        else s = (A.f-A.s+1)*(B.f-B.s+1)-1;
    }
    return ret;
}

Compilation message

seats.cpp: In function 'void upd(ll, ll, ll, ll, ll, ll)':
seats.cpp:15:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     ll m = s+e>>1;
      |             ^
seats.cpp: In function 'std::pair<int, int> hap(ll, ll, ll, ll, ll, ll)':
seats.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     ll m = s+e>>1;
      |             ^
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0 ; i < r.size() ; i++) X.push_back({r[i],c[i]});
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 7 ms 380 KB Output is correct
5 Correct 59 ms 332 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 9 ms 352 KB Output is correct
8 Correct 12 ms 376 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 7 ms 364 KB Output is correct
12 Correct 57 ms 360 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 7 ms 380 KB Output is correct
5 Correct 59 ms 332 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 9 ms 352 KB Output is correct
8 Correct 12 ms 376 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 7 ms 364 KB Output is correct
12 Correct 57 ms 360 KB Output is correct
13 Correct 24 ms 1240 KB Output is correct
14 Correct 17 ms 1156 KB Output is correct
15 Correct 19 ms 1236 KB Output is correct
16 Execution timed out 4066 ms 1176 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 56772 KB Output is correct
2 Correct 1041 ms 56720 KB Output is correct
3 Execution timed out 4050 ms 56764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1240 KB Output is correct
2 Correct 200 ms 6628 KB Output is correct
3 Execution timed out 4078 ms 56780 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1328 KB Output is correct
2 Correct 40 ms 1320 KB Output is correct
3 Correct 564 ms 1316 KB Output is correct
4 Execution timed out 4059 ms 1108 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 7 ms 380 KB Output is correct
5 Correct 59 ms 332 KB Output is correct
6 Correct 6 ms 380 KB Output is correct
7 Correct 9 ms 352 KB Output is correct
8 Correct 12 ms 376 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 7 ms 364 KB Output is correct
12 Correct 57 ms 360 KB Output is correct
13 Correct 24 ms 1240 KB Output is correct
14 Correct 17 ms 1156 KB Output is correct
15 Correct 19 ms 1236 KB Output is correct
16 Execution timed out 4066 ms 1176 KB Time limit exceeded
17 Halted 0 ms 0 KB -