oj.uz

Submission #904934

# Submission time Handle Problem Language Result Execution time Memory
904934 2024-01-12T11:36:14 Z Trisanu_Das Seats (IOI18_seats) C++17
25 / 100
 4000 ms 85856 KB 
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b,c,d;
} val[4000100];
int l[4000100], r[4000100];
node join(node a, node b){
    node c;
    c.a = min(a.a,b.a);
    c.b = max(a.b,b.b);
    c.c = min(a.c,b.c);
    c.d = max(a.d,b.d);
    return c;
}
void build(int i, int rl, int rr) {
    l[i] = rl, r[i] = rr;
    if(rl!=rr)
        build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, rr);
}
void upd(int i, int pos, int x, int y) {
    if(l[i]==r[i])
        return(void) (val[i].a=val[i].b=x,val[i].c=val[i].d=y);
    if(pos>r[i*2])
        upd(i*2+1,pos,x,y);
    else upd(i*2,pos,x,y);
    val[i]=join(val[i*2],val[i*2+1]);
}
node query(int i, int x, int y) {
    if(x<=l[i]&&r[i]<=y)
        return val[i];
    if(x>r[i]||l[i]>y)
        return (node){100000,0,100000,0};
    return join(query(i*2,x,y),query(i*2+1,x,y));
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    build(1,1,H*W);
    for(int i = 0; i < r[1]; i++) {
        upd(1,i+1,R[i],C[i]);
    }
}
int swap_seats(int a, int b) {
    a++,b++;
    node x = query(1,a,a), y = query(1,b,b);
    upd(1,b,x.a,x.c);
    upd(1,a,y.a,y.c);
    int ans = 0;
    for(int i = 1; i <= r[1]; i++) {
        x=query(1,1,i);
        int sz = (x.b-x.a+1)*(x.d-x.c+1);
        if(sz==i) ans++;
        else i = sz-1;
    }
    return ans;
}

Compilation message

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:19:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, rr);
      |                      ~~^~~
seats.cpp:19:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         build(i*2,rl,rr+rl>>1),build(i*2+1,rl+rr+2>>1, rr);
      |                                            ~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 6 ms 4440 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 20 ms 4612 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct
8 Correct 7 ms 4440 KB Output is correct
9 Correct 7 ms 4636 KB Output is correct
10 Correct 4 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 20 ms 4624 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 6 ms 4440 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 20 ms 4612 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct
8 Correct 7 ms 4440 KB Output is correct
9 Correct 7 ms 4636 KB Output is correct
10 Correct 4 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 20 ms 4624 KB Output is correct
13 Correct 11 ms 4696 KB Output is correct
14 Correct 9 ms 4700 KB Output is correct
15 Correct 9 ms 4700 KB Output is correct
16 Execution timed out 4003 ms 4696 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 69460 KB Output is correct
2 Correct 335 ms 85576 KB Output is correct
3 Correct 2964 ms 85856 KB Output is correct
4 Correct 469 ms 85624 KB Output is correct
5 Correct 423 ms 85632 KB Output is correct
6 Correct 3432 ms 85640 KB Output is correct
7 Correct 1036 ms 85620 KB Output is correct
8 Correct 544 ms 85592 KB Output is correct
9 Correct 2706 ms 85648 KB Output is correct
10 Correct 1611 ms 85632 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4700 KB Output is correct
2 Correct 75 ms 14172 KB Output is correct
3 Correct 2240 ms 69456 KB Output is correct
4 Correct 331 ms 85588 KB Output is correct
5 Execution timed out 4013 ms 85588 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5588 KB Output is correct
2 Correct 24 ms 5552 KB Output is correct
3 Correct 197 ms 5408 KB Output is correct
4 Correct 2032 ms 5756 KB Output is correct
5 Correct 79 ms 5728 KB Output is correct
6 Incorrect 1143 ms 69956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 6 ms 4440 KB Output is correct
3 Correct 4 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 20 ms 4612 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct
8 Correct 7 ms 4440 KB Output is correct
9 Correct 7 ms 4636 KB Output is correct
10 Correct 4 ms 4444 KB Output is correct
11 Correct 5 ms 4444 KB Output is correct
12 Correct 20 ms 4624 KB Output is correct
13 Correct 11 ms 4696 KB Output is correct
14 Correct 9 ms 4700 KB Output is correct
15 Correct 9 ms 4700 KB Output is correct
16 Execution timed out 4003 ms 4696 KB Time limit exceeded
17 Halted 0 ms 0 KB -