Submission #1073823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073823		HorizonWest	Seats (IOI18_seats)	C++17	11 / 100	4078 ms	58120 KiB

seats

#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
using namespace std;

#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

vector <pair<int, int>> v; 

struct STMIN
{
    vector <int> tree; int l;

    int update(int k, int v){
        k += (l-1); tree[k] = v;
        for(k/= 2; k > 0; k /= 2){
            tree[k] = min(tree[2*k], tree[2*k+1]);
        }
    }

    int query(int k, int x, int y, int s, int e){
        if(s > y || e < x) return Inf;
        
        if(s >= x && e <= y){
            return tree[k];
        }
        int mid = (s + e) / 2; 
        return min(query(2*k, x, y, s, mid), 
            query(2*k+1, x, y, mid+1, e));
    }

    int query(int x, int y) {
        return query(1, x, y, 1, l);
    }

    STMIN(int n){
        for(l = 1; l < n; l*= 2);
        tree.assign(2*l+1, 0);
    }
};

struct STMAX
{
    vector <int> tree; int l;

    int update(int k, int v){
        k += (l-1); tree[k] = v;
        for(k/= 2; k > 0; k /= 2){
            tree[k] = max(tree[2*k], tree[2*k+1]);
        }
    }

    int query(int k, int x, int y, int s, int e){
        if(s > y || e < x) return 0;
        if(s >= x && e <= y){
            return tree[k];
        }
        int mid = (s + e) / 2; 
        return max(query(2*k, x, y, s, mid), 
            query(2*k+1, x, y, mid+1, e));
    }

    int query(int x, int y) {
        return query(1, x, y, 1, l);
    }

    STMAX(int n){
        for(l = 1; l < n; l*= 2);
        tree.assign(2*l+1, 0);
    }
};

STMIN Sa(Max), Sc(Max);
STMAX Sb(Max), Sd(Max);

void update(int x){
    Sa.update(x, v[x].fs);
    Sb.update(x, v[x].fs);
    Sc.update(x, v[x].sd);
    Sd.update(x, v[x].sd);
}

void show(int a, int b){
    cerr << Sa.query(a, b) << endl;
    cerr << Sb.query(a, b) << endl;
    cerr << Sc.query(a, b) << endl;
    cerr << Sd.query(a, b) << endl;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
    v.push_back({ 0, 0 });

    for(int i = 0; i < H*W; i++){
        v.push_back({ R[i], C[i] });
        //update(i+1);
    }
}

/*
1- 1 1
2- 1 2
3- 0 2
4- 0 1
5- 0 0
6- 2 1
7- 2 2
8- 1 0
9- 2 0
*/

int tmp(int A, int B)
{
    A++; B++; swap(v[A], v[B]); 
    int a = Inf, b = 0, c = Inf, d = 0, ans = 0;

    for(int i = 1; i < v.size(); i++)
    {
        a = min(a, v[i].fs);
        b = max(b, v[i].fs);
        c = min(c, v[i].sd);
        d = max(d, v[i].sd);
        int fx = (b-a+1) * (d-c+1);
        ///if(B == 7) cerr << a << " " << b << " " << c << " " << d << endl;
        ans += (fx == i);
    }
    //swap(v[A], v[B]);
    return ans;
}

int swap_seats(int A, int B) {
    A++; B++; 
    
    swap(v[A], v[B]);
   // update(A); update(B);

    int a = Inf, b = 0, c = Inf, d = 0, ans = 0, j = 0;

    for(int i = 1; i < v.size(); i++)
    {
        if(j >= i){
            return -1;
        }

        if(j != i-1){
            a = Sa.query(1, i);
            b = Sb.query(1, i);
            c = Sc.query(1, i);
            d = Sd.query(1, i);
        } else {
            a = min(a, v[i].fs);
            b = max(b, v[i].fs);
            c = min(c, v[i].sd);
            d = max(d, v[i].sd);
        }

        j = i;

        int fx = (b-a+1) * (d-c+1);
    
        if(i == fx){
            ans++;
        }else{
            if(abs(i - fx) > 300){
                //i = fx - 1;
            }
        }
    }


    return ans;
}

Compilation message (stderr)

seats.cpp: In member function 'int STMIN::update(int, int)':
seats.cpp:41:5: warning: no return statement in function returning non-void [-Wreturn-type]
   41 |     }
      |     ^
seats.cpp: In member function 'int STMAX::update(int, int)':
seats.cpp:73:5: warning: no return statement in function returning non-void [-Wreturn-type]
   73 |     }
      |     ^
seats.cpp: In function 'int tmp(int, int)':
seats.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i = 1; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:161:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i = 1; i < v.size(); i++)
      |                    ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30