oj.uz

Submission #145141

# Submission time Handle Problem Language Result Execution time Memory
145141 2019-08-18T21:33:40 Z jacynkaa Rectangles (IOI19_rect) C++14
0 / 100
 638 ms 600536 KB 
#include <bits/stdc++.h>
#include <math.h>
#include <chrono>
using namespace std;
#pragma GCC optimize("-O3")
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10) //cin.tie(0); cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define what(x) cerr << #x << " is " << x << endl;

const int MAXN = 2505;

vector<int> prawo[MAXN][MAXN];
vector<int> dol[MAXN][MAXN];
vector<pii> R[MAXN][MAXN];
vector<pii> D[MAXN][MAXN];
int n, m;
int tab[MAXN][MAXN];
long long ans = 0;

void wypelnij1(vector<int> (&P)[MAXN][MAXN])
{
    rep(i, n)
    {
        vector<pii> X;
        rep(j, m)
            X.pb({tab[i][j], j});
        sort(all(X));
        reverse(all(X));
        set<pii> S;
        int j = 0;
        while (j < X.size())
        {
            int k = j;

            while (k + 1 < X.size() && X[j].nd == X[k + 1].nd)
                k++;
            for (int l = j; l <= k; l++)
            {
                // cerr << X[l].nd << " " << X[l].st << endl;
                S.insert({X[l].nd, X[l].st});
            }
            for (int l = j; l <= k; l++)
            {
                auto r = S.find({X[l].nd, X[l].st});
                auto q = (r == S.begin()) ? r : next(r, -1);
                auto s = (next(r, 1) == S.end()) ? r : next(r, 1);

                //   cerr << q->st << " " << r->st << " " << s->st << endl;

                if (r->st - q->st - 1 > 0) //popraawic!!!!
                {
                    P[i][q->st].pb(r->st - q->st - 1);
                    //cerr << q->st << " ech1 " << r->st << endl;
                }

                if (s->st - r->st - 1 > 0)
                {
                    P[i][r->st].pb(s->st - r->st - 1);
                    //cerr << s->st << " ech2 " << r->st << endl;
                }
            }
            j = k + 1;
        }
    }
}
void wypelnij2(vector<int> (&zrodlo)[MAXN][MAXN], vector<pii> (&ujscie)[MAXN][MAXN])
{
    rep(j, m)
    {
        vector<pii> X(3e3, {-1, -1});
        for (int i = n - 1; i >= 0; i--)
            for (int a : zrodlo[i][j])
            {
                X[a] = (X[a].st == i + 1) ? mp(i, X[a].nd + 1) : mp(i, 1);
                ujscie[i][j].pb({a, X[a].nd});
            }
    }
}

void obroc()
{
    rep(i, n) rep(j, m) if (i > j) swap(tab[i][j], tab[j][i]), swap(D[i][j], D[j][i]), swap(dol[i][j], dol[j][i]);
    swap(n, m);
}

void solve(int i, int j)
{
    for (auto A : D[i][j + 1])
        for (auto B : R[i + 1][j])
            if (B.nd >= A.st && A.nd >= B.st)
            {
                // cout << "tuutaj:" << i << " " << j << endl;
                ans++;
            }
}

long long count_rectangles(vector<vector<int>> A)
{
    n = A.size();
    m = A[0].size();
    rep(i, n) rep(j, m) tab[i][j] = A[i][j];
    wypelnij1(prawo);
    wypelnij2(prawo, R);
    obroc();
    wypelnij1(dol);
    wypelnij2(dol, D);
    obroc();
    /*
    rep(i, n)
    {
        rep(j, m)
        {
            cout << i << " " << j << ":::    ";
            for (auto a : D[i][j])
                cout << a.st << " " << a.nd << "                ";
            // cout << a << "              /// ";
        }
        cout << endl;
    }
    cout << "adjsff" << endl;
    rep(i, n)
    {
        rep(j, m)
        {
            cout << i << " " << j << ":::    ";
            for (auto a : R[i][j])
                cout << a.st << " " << a.nd << "                ";
            // cout << a << "              /// ";
        }
        cout << endl;
    }
    */
    rep(i, n - 1) rep(j, m - 1) solve(i, j);
    return ans;
}
/* 
main()
{
    _upgrade;
    cout << count_rectangles({{4, 8, 7, 5, 6},
                              {7, 4, 10, 3, 5},
                              {9, 7, 20, 14, 2},
                              {9, 14, 7, 3, 6},
                              {5, 7, 5, 2, 7},
                              {4, 5, 13, 5, 6}})
         << endl;
}
*/

Compilation message

rect.cpp: In function 'void wypelnij1(std::vector<int> (&)[2505][2505])':
rect.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < X.size())
                ~~^~~~~~~~~~
rect.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (k + 1 < X.size() && X[j].nd == X[k + 1].nd)
                    ~~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 589752 KB Output is correct
2 Correct 598 ms 590048 KB Output is correct
3 Correct 548 ms 589988 KB Output is correct
4 Correct 554 ms 590072 KB Output is correct
5 Correct 574 ms 589944 KB Output is correct
6 Correct 550 ms 590072 KB Output is correct
7 Incorrect 571 ms 590124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 589752 KB Output is correct
2 Correct 598 ms 590048 KB Output is correct
3 Correct 548 ms 589988 KB Output is correct
4 Correct 554 ms 590072 KB Output is correct
5 Correct 574 ms 589944 KB Output is correct
6 Correct 550 ms 590072 KB Output is correct
7 Incorrect 571 ms 590124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 589752 KB Output is correct
2 Correct 598 ms 590048 KB Output is correct
3 Correct 548 ms 589988 KB Output is correct
4 Correct 554 ms 590072 KB Output is correct
5 Correct 574 ms 589944 KB Output is correct
6 Correct 550 ms 590072 KB Output is correct
7 Incorrect 571 ms 590124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 589752 KB Output is correct
2 Correct 598 ms 590048 KB Output is correct
3 Correct 548 ms 589988 KB Output is correct
4 Correct 554 ms 590072 KB Output is correct
5 Correct 574 ms 589944 KB Output is correct
6 Correct 550 ms 590072 KB Output is correct
7 Incorrect 571 ms 590124 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 570 ms 600536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 555 ms 589852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 589752 KB Output is correct
2 Correct 598 ms 590048 KB Output is correct
3 Correct 548 ms 589988 KB Output is correct
4 Correct 554 ms 590072 KB Output is correct
5 Correct 574 ms 589944 KB Output is correct
6 Correct 550 ms 590072 KB Output is correct
7 Incorrect 571 ms 590124 KB Output isn't correct
8 Halted 0 ms 0 KB -