oj.uz

Submission #914905

# Submission time Handle Problem Language Result Execution time Memory
914905 2024-01-22T20:48:25 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 1164 ms 210724 KB 
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 1000006;

#define X first.first
#define Y first.second
#define I second
#define pt pair<pair<int,int>, int>

int n, k;
int ans[N];
pt p[N];
vector<pt> y[N], x[N];
int used_x[N];
set<int> last_x[N];
int ly[N], ry[N];

void lesgo(int i, int ax)
{
    int pos;
    if (used_x[ax] == 3)
    {
        used_x[ax]--;
        int last_y;
        auto it = last_x[ax].lower_bound(i);
        --it;
        last_y = *it;

        if (ly[last_y] == ry[last_y])
        {
            last_x[y[last_y][ly[last_y]].X].erase(last_y);
            ly[last_y]++;
        }
        else if (y[last_y][ly[last_y]].X == ax)
        {
            pos = ly[last_y];
            last_x[y[last_y][pos].X].erase(last_y);
            pos++;
			ly[last_y] = pos;
            if (pos < ry[last_y])
            {
				used_x[y[last_y][pos].X]++;
				lesgo(last_y, y[last_y][pos].X);
                last_x[y[last_y][pos].X].insert(last_y);
			}
        }
        else if(y[last_y][ry[last_y]].X == ax)
        {
            pos = ry[last_y];
            last_x[y[last_y][pos].X].erase(last_y);
            pos--;
            ry[last_y] = pos;
            if (pos > ly[last_y])
            {
                used_x[y[last_y][pos].X]++;
				lesgo(last_y, y[last_y][pos].X);
                last_x[y[last_y][pos].X].insert(last_y);
            }
        }
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].X >> p[i].Y;
        k = max(k, max(p[i].X, p[i].Y));
        p[i].I = i;
        y[p[i].Y].PB(p[i]);
        x[p[i].X].PB(p[i]);
    }

    for (int i = 1; i <= k; i++)
    {
        sort(all(y[i]));
        sort(all(x[i]), [](pt a, pt b) {return a.Y < b.Y; });
    }

    for (int i = 1; i <= k; i++)
    {
       if(y[i].empty())
           continue;

       used_x[y[i][0].X]++;
       ly[i] = 0;
       last_x[y[i][0].X].insert(i);
       lesgo(i, y[i][0].X);


       ry[i] = y[i].size() - 1;
       if (ly[i] != ry[i])
       {
           used_x[y[i].back().X]++;
           last_x[y[i].back().X].insert(i);
           lesgo(i, y[i].back().X);
       }
    }


    for (int i = 1; i <= k; i++)
    {
        if(y[i].empty())
            continue;
        if(ly[i] <= ry[i])
            ans[y[i][ly[i]].I] = ans[y[i][ry[i]].I] = 1;
    }


    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << endl;

}


int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*

9
2 1
5 1
1 2
2 2
3 2
4 2
2 3
3 4
4 4

9
1 1
1 2
2 2
1 3
1 4
1 5
2 5
1 6
1 7


20
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
1 5
2 5
3 5
4 5

 


16
1 1
2 1
3 1
4 1
1 2
2 2
4 2
1 3
2 3
3 3
4 3
1 4
4 4
1 5
2 5
3 5


*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 107100 KB Output is correct
2 Correct 31 ms 104980 KB Output is correct
3 Correct 39 ms 103004 KB Output is correct
4 Correct 35 ms 98904 KB Output is correct
5 Correct 36 ms 98136 KB Output is correct
6 Correct 37 ms 100948 KB Output is correct
7 Correct 35 ms 100956 KB Output is correct
8 Correct 38 ms 98828 KB Output is correct
9 Correct 33 ms 98136 KB Output is correct
10 Correct 38 ms 98136 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 107100 KB Output is correct
2 Correct 31 ms 104980 KB Output is correct
3 Correct 39 ms 103004 KB Output is correct
4 Correct 35 ms 98904 KB Output is correct
5 Correct 36 ms 98136 KB Output is correct
6 Correct 37 ms 100948 KB Output is correct
7 Correct 35 ms 100956 KB Output is correct
8 Correct 38 ms 98828 KB Output is correct
9 Correct 33 ms 98136 KB Output is correct
10 Correct 38 ms 98136 KB Output is correct
11 Correct 36 ms 98952 KB Output is correct
12 Correct 36 ms 98904 KB Output is correct
13 Correct 37 ms 98904 KB Output is correct
14 Correct 38 ms 100952 KB Output is correct
15 Incorrect 38 ms 100948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 102804 KB Output is correct
2 Correct 51 ms 103600 KB Output is correct
3 Correct 81 ms 111560 KB Output is correct
4 Correct 152 ms 128080 KB Output is correct
5 Correct 49 ms 105300 KB Output is correct
6 Correct 33 ms 101980 KB Output is correct
7 Correct 158 ms 125632 KB Output is correct
8 Correct 109 ms 118864 KB Output is correct
9 Correct 243 ms 139516 KB Output is correct
10 Correct 193 ms 131152 KB Output is correct
11 Correct 224 ms 138712 KB Output is correct
12 Correct 219 ms 138580 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 159828 KB Output is correct
2 Correct 445 ms 162820 KB Output is correct
3 Correct 462 ms 159828 KB Output is correct
4 Correct 436 ms 159828 KB Output is correct
5 Correct 440 ms 159692 KB Output is correct
6 Correct 1115 ms 210672 KB Output is correct
7 Correct 1150 ms 210720 KB Output is correct
8 Correct 1105 ms 210636 KB Output is correct
9 Correct 1164 ms 210704 KB Output is correct
10 Correct 1100 ms 210724 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 107100 KB Output is correct
2 Correct 31 ms 104980 KB Output is correct
3 Correct 39 ms 103004 KB Output is correct
4 Correct 35 ms 98904 KB Output is correct
5 Correct 36 ms 98136 KB Output is correct
6 Correct 37 ms 100948 KB Output is correct
7 Correct 35 ms 100956 KB Output is correct
8 Correct 38 ms 98828 KB Output is correct
9 Correct 33 ms 98136 KB Output is correct
10 Correct 38 ms 98136 KB Output is correct
11 Correct 36 ms 98952 KB Output is correct
12 Correct 36 ms 98904 KB Output is correct
13 Correct 37 ms 98904 KB Output is correct
14 Correct 38 ms 100952 KB Output is correct
15 Incorrect 38 ms 100948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 107100 KB Output is correct
2 Correct 31 ms 104980 KB Output is correct
3 Correct 39 ms 103004 KB Output is correct
4 Correct 35 ms 98904 KB Output is correct
5 Correct 36 ms 98136 KB Output is correct
6 Correct 37 ms 100948 KB Output is correct
7 Correct 35 ms 100956 KB Output is correct
8 Correct 38 ms 98828 KB Output is correct
9 Correct 33 ms 98136 KB Output is correct
10 Correct 38 ms 98136 KB Output is correct
11 Correct 36 ms 98952 KB Output is correct
12 Correct 36 ms 98904 KB Output is correct
13 Correct 37 ms 98904 KB Output is correct
14 Correct 38 ms 100952 KB Output is correct
15 Incorrect 38 ms 100948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 107100 KB Output is correct
2 Correct 31 ms 104980 KB Output is correct
3 Correct 39 ms 103004 KB Output is correct
4 Correct 35 ms 98904 KB Output is correct
5 Correct 36 ms 98136 KB Output is correct
6 Correct 37 ms 100948 KB Output is correct
7 Correct 35 ms 100956 KB Output is correct
8 Correct 38 ms 98828 KB Output is correct
9 Correct 33 ms 98136 KB Output is correct
10 Correct 38 ms 98136 KB Output is correct
11 Correct 36 ms 98952 KB Output is correct
12 Correct 36 ms 98904 KB Output is correct
13 Correct 37 ms 98904 KB Output is correct
14 Correct 38 ms 100952 KB Output is correct
15 Incorrect 38 ms 100948 KB Output isn't correct
16 Halted 0 ms 0 KB -