oj.uz

Submission #334481

# Submission time Handle Problem Language Result Execution time Memory
334481 2020-12-09T08:13:36 Z ncduy0303 RMQ (NOI17_rmq) C++17
100 / 100
 52 ms 12140 KB 
/*
Solution: 
    1- merge all queries with fixed answer (we will use sorting before merging), if they aren't connected then there is no answer
    2- iterate over values from n-1 to 0, we know it consisted of the intersection of smaller ranges,
        so our current value i should be put in any index in the intersection of all its ranges,
        if there is no such index then there is no answer
    3- after we added the value i, we can fill our range with unselected vaules that are strictly greater than i, if there is no 
        enough values of them then there is no answer, because the values of elements in our current range has a minimum value i
    4- there may be some remaining numbers, we can handle them if we add the query (0 , n-1 , 0), it forces the solution to solve it
        filling the empty indices, and finishing the solution
    O(N log N)
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n, m;
int a[N], b[N], c[N], A[N];
int o[N];
bool vis[N];
vector<pair<int, int>> adj[N], adj2[N];


struct DSU{
    vector<int> fat ; 
    void init(int n){
        fat.resize(n) ; 
        for(int i = 0 ; i < n; i++){
            fat[i] = i ;
        }
    }
    int fin(int x){
        return fat[x] = (fat[x]==x?x:fin(fat[x]));
    }
    void unio(int a , int b){
        int aa = fin(a) ; 
        int bb = fin(b) ; 
        if(aa!=bb){
            fat[aa] = bb ; 
        }
    }
    bool same(int A , int B){
        return fin(A) == fin(B) ; 
    }
} d , ava; 

void no()
{
        for (int i = 0; i < n; i++)
        {
                cout << -1 << " ";
        }
        exit(0);
}

void verify()
{
        for (int i = 0; i < m; i++)
        {
                int mn = N;
                for (int j = a[i]; j <= b[i]; j++)
                {
                        mn = min(mn, A[j]);
                }
                if (mn != c[i])
                {
                        no();
                }
        }
        for(int i = 0 ; i< n;i++){
                if(o[A[i]]++ == 1){
                        no() ; 
                }
        }
}

void print()
{
        for (int i = 0; i < n; i++)
        {
                cout << A[i] << " ";
        }
}

int l[N], r[N];
int L[N], R[N];


void block(int i){
        vis[i] = 1; 
        d.unio(i , i+1) ;
        ava.unio(A[i] , A[i] -1) ; 
}

int nxt(int x){
        return d.fin(x) ;
}

pair<int  , int > prs[N] ;

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        memset(l, -1, sizeof l);
        memset(r, -1, sizeof r);

        cin >> n >> m;
        d.init(n+10) ; 
        ava.init(n+10) ; 
        for(int i = 0 ;i < n;i++){
                L[i] = -N ; 
                R[i] = N ; 
        }
        for(int i = 0 ; i < n;i++){
                prs[i] = {N , N} ; 
        }
        
        for (int i = 0; i < m; i++)
        {
                cin >> a[i] >> b[i] >> c[i];
                adj[c[i]].push_back({a[i], b[i]});
                prs[c[i]] = min(prs[c[i]] , adj[c[i]].back()) ; 
        }
        adj[0].push_back({0 , n-1}) ; 

        for (int i = 0; i < n; i++)
        {
                if (adj[i].empty())
                        continue;
                sort(adj[i].begin(), adj[i].end());
        
                L[i] = l[i] = adj[i][0].first;
                R[i] = r[i] = adj[i][0].second;

                for (int j = 0; j < adj[i].size(); j++)
                {
                        int li = adj[i][j].first;
                        int ri = adj[i][j].second;
                        L[i] = max(L[i] , li) ; 
                        R[i] = min(R[i] , ri) ; 
                        if(L[i] > R[i])
                                no() ; 
                        if (li > r[i] + 1)
                                no();
                        r[i] = max(r[i], ri);
                }
                adj2[l[i]].push_back({r[i], i});
        }
        for(int i = n-1 ;i >= 0 ;i --){
                if(l[i] < 0)continue ;
                bool k = 0 ;
                for(int j = L[i] ;j <=R[i] ;j  = nxt(j+1) ){
                        if(!vis[j]){
                                A[j] = i ; 
                                block(j) ;  
                                k = 1;
                                break ; 
                        }
                }
                if(!k)no() ; 
                for(int j = nxt(l[i]) ;j<=r[i] ; j  = nxt(j+1) ){
                        if(vis[j]) continue ; 
                        int u = ava.fin(n-1) ;
                        if(u < i){
                                no() ; 
                        }
                        A[j] = u ;                        
                        block(j) ;
                }
        }
        //verify() ;
        print() ; 
        return 0;
}

Compilation message

rmq.cpp: In function 'int main()':
rmq.cpp:138:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                 for (int j = 0; j < adj[i].size(); j++)
      |                                 ~~^~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 4 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 5 ms 5888 KB Output is correct
10 Correct 4 ms 5868 KB Output is correct
11 Correct 4 ms 5868 KB Output is correct

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 4 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 5 ms 5888 KB Output is correct
10 Correct 4 ms 5868 KB Output is correct
11 Correct 4 ms 5868 KB Output is correct
12 Correct 5 ms 5868 KB Output is correct
13 Correct 5 ms 5868 KB Output is correct
14 Correct 4 ms 5868 KB Output is correct
15 Correct 5 ms 5868 KB Output is correct
16 Correct 5 ms 5868 KB Output is correct
17 Correct 5 ms 5868 KB Output is correct
18 Correct 5 ms 5868 KB Output is correct
19 Correct 4 ms 5868 KB Output is correct
20 Correct 4 ms 5868 KB Output is correct
21 Correct 4 ms 5868 KB Output is correct
22 Correct 4 ms 5888 KB Output is correct
23 Correct 4 ms 5996 KB Output is correct
24 Correct 5 ms 5868 KB Output is correct
25 Correct 4 ms 5868 KB Output is correct
26 Correct 4 ms 5868 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 4 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 5 ms 5888 KB Output is correct
10 Correct 4 ms 5868 KB Output is correct
11 Correct 4 ms 5868 KB Output is correct
12 Correct 5 ms 5868 KB Output is correct
13 Correct 5 ms 5868 KB Output is correct
14 Correct 4 ms 5868 KB Output is correct
15 Correct 5 ms 5868 KB Output is correct
16 Correct 5 ms 5868 KB Output is correct
17 Correct 5 ms 5868 KB Output is correct
18 Correct 5 ms 5868 KB Output is correct
19 Correct 4 ms 5868 KB Output is correct
20 Correct 4 ms 5868 KB Output is correct
21 Correct 4 ms 5868 KB Output is correct
22 Correct 4 ms 5888 KB Output is correct
23 Correct 4 ms 5996 KB Output is correct
24 Correct 5 ms 5868 KB Output is correct
25 Correct 4 ms 5868 KB Output is correct
26 Correct 4 ms 5868 KB Output is correct
27 Correct 49 ms 11736 KB Output is correct
28 Correct 50 ms 11564 KB Output is correct
29 Correct 37 ms 10856 KB Output is correct
30 Correct 48 ms 11896 KB Output is correct
31 Correct 39 ms 10852 KB Output is correct
32 Correct 52 ms 12004 KB Output is correct
33 Correct 18 ms 9452 KB Output is correct
34 Correct 13 ms 7916 KB Output is correct
35 Correct 21 ms 9472 KB Output is correct
36 Correct 38 ms 11116 KB Output is correct
37 Correct 50 ms 12140 KB Output is correct
38 Correct 11 ms 7788 KB Output is correct
39 Correct 37 ms 10700 KB Output is correct
40 Correct 4 ms 5868 KB Output is correct
41 Correct 4 ms 5868 KB Output is correct