oj.uz

Submission #83517

# Submission time Handle Problem Language Result Execution time Memory
83517 2018-11-08T17:05:37 Z nikolapesic2802 Long Mansion (JOI17_long_mansion) C++14
0 / 100
 294 ms 18984 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ///find_by_order(),order_of_key()
const int N=5*1e5+5;
vector<int> hi(N),lo(N),l(N),r(N);
bool on(int l,int r,int x){return x>=l&&x<=r;}
bool can(int l,int r,int x){return (hi[x]&&on(l,r,hi[x]))||(lo[x]&&on(l,r,lo[x]));}
int main()
{
    int n;
    scanf("%i",&n);
    vector<int> cor(n-1);
    for(int i=0;i<n-1;i++)
        scanf("%i",&cor[i]);
    vector<vector<int> > sobe(n);
    for(int i=0;i<n;i++)
    {
        int b;
        scanf("%i",&b);
        for(int j=0;j<b;j++)
        {
            int a;
            scanf("%i",&a);
            sobe[i].pb(a);
        }
    }
    vector<int> keys(n,-1);
    for(int i=0;i<n-1;i++)
    {
        for(auto p:sobe[i])
            keys[p]=i;
        lo[i]=keys[cor[i]];
    }
    fill(keys.begin(),keys.end(),-1);
    for(int i=n-1;i>0;i--)
    {
        for(auto p:sobe[i])
            keys[p]=i;
        hi[i-1]=keys[cor[i-1]];
    }
    for(int i=0;i<n;i++)
    {
        l[i]=r[i]=i;
        while(true)
        {
            if(l[i]>0&&can(l[i],r[i],l[i]-1))
            {
                r[i]=max(r[i],r[l[i]-1]);
                l[i]=l[l[i]-1];
            }
            else
                if(r[i]<n-1&&can(l[i],r[i],r[i]))
                    r[i]++;
                else
                    break;
        }
    }
    int q;
    scanf("%i",&q);
    for(int i=0;i<q;i++)
    {
        int x,y;
        scanf("%i %i",&x,&y);
        x--;
        y--;
        if(on(l[x],r[x],y))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
long_mansion.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&cor[i]);
         ~~~~~^~~~~~~~~~~~~~
long_mansion.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&b);
         ~~~~~^~~~~~~~~
long_mansion.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&a);
             ~~~~~^~~~~~~~~
long_mansion.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
long_mansion.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8444 KB Output is correct
2 Correct 12 ms 8508 KB Output is correct
3 Incorrect 12 ms 8916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8444 KB Output is correct
2 Correct 12 ms 8508 KB Output is correct
3 Incorrect 12 ms 8916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 18788 KB Output is correct
2 Correct 293 ms 18880 KB Output is correct
3 Correct 274 ms 18984 KB Output is correct
4 Correct 294 ms 18984 KB Output is correct
5 Correct 281 ms 18984 KB Output is correct
6 Incorrect 243 ms 18984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8444 KB Output is correct
2 Correct 12 ms 8508 KB Output is correct
3 Incorrect 12 ms 8916 KB Output isn't correct
4 Halted 0 ms 0 KB -