oj.uz

Submission #85812

# Submission time Handle Problem Language Result Execution time Memory
85812 2018-11-21T15:00:28 Z nikolapesic2802 Abduction 2 (JOI17_abduction2) C++14
13 / 100
 18 ms 7128 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
	os << '{';
	for(int i=0;i<sz(a);i++)
	{
		if(i>0&&i<sz(a)-1)
			os << ", ";
		os << a[i];
	}
	os << '}';
    return os;
}
int h,w;
const int N=5e4+5;
int sparce[2][2][N][20];
vector<int> ver(N),hor(N);
map<int,int> memo[2][N];///0-up,down, 1-levo,desno;
///0,0 up  0,1 down 1,0 left
int up(int tr,int v)
{
    for(int j=0;j<20;j++)
    {
        if(sparce[0][0][tr][j]>v)
        {
            if(j==0)
                return tr-1;
            else
                return up(tr-(1<<(j-1)),v);
        }
    }
    return -1;
}
int down(int tr,int v)
{
    for(int j=0;j<20;j++)
    {
        if(sparce[0][1][tr][j]>v)
        {
            if(j==0)
                return tr+1;
            else
                return down(tr+(1<<(j-1)),v);
        }
    }
    return -1;
}
int left(int tr,int v)
{
    for(int j=0;j<20;j++)
    {
        if(sparce[1][0][tr][j]>v)
        {
            if(j==0)
                return tr-1;
            else
                return left(tr-(1<<(j-1)),v);
        }
    }
    return -1;
}
int right(int tr,int v)
{
    for(int j=0;j<20;j++)
    {
        if(sparce[1][1][tr][j]>v)
        {
            if(j==0)
                return tr+1;
            else
                return right(tr+(1<<(j-1)),v);
        }
    }
    return -1;
}
int calc(int x,int y,int br)
{
    if(memo[br][x][y]!=0)
        return memo[br][x][y];
    //printf("Usao za %i %i %i\n",x,y,br);
    if(br==0)
    {
        int upp=up(x,ver[y]);
        int downn=down(x,ver[y]);
        //printf("Up: %i, down: %i\n",upp,downn);
        if(upp==-1)
        {
            memo[br][x][y]=x;
        }
        else
        {
            memo[br][x][y]=calc(upp,y,1)+x-upp;
        }

        if(downn==-1)
        {
            memo[br][x][y]=max(memo[br][x][y],h-1-x);
        }
        else
        {
            memo[br][x][y]=max(memo[br][x][y],calc(downn,y,1)+downn-x);
        }
    }
    else
    {
        int levo=left(y,hor[x]);
        int desno=right(y,hor[x]);
        //printf("Levo: %i, desno: %i\n",levo,desno);
        if(levo==-1)
        {
            memo[br][x][y]=y;
        }
        else
        {
            memo[br][x][y]=calc(x,levo,0)+y-levo;
        }
        if(desno==-1)
        {
            memo[br][x][y]=max(memo[br][x][y],w-1-y);
        }
        else
        {
            memo[br][x][y]=max(memo[br][x][y],calc(x,desno,0)+desno-y);
        }
    }
    return memo[br][x][y];
}

int main()
{
	int q;
	scanf("%i %i %i",&h,&w,&q);
	for(int i=0;i<h;i++)
        scanf("%i",&hor[i]);
    sparce[0][0][0][0]=-1;
    for(int i=1;i<h;i++)
    {
        sparce[0][0][i][0]=hor[i-1];
    }
    for(int j=1;j<20;j++)
    {
        int m=1<<(j-1);
        for(int i=0;i<h;i++)
        {
            if(i-m<0)
                continue;
            sparce[0][0][i][j]=max(sparce[0][0][i-m][j-1],sparce[0][0][i][j-1]);
        }
    }
    sparce[0][1][h-1][0]=-1;
    for(int i=0;i<h-1;i++)
    {
        sparce[0][1][i][0]=hor[i+1];
    }
    for(int j=1;j<20;j++)
    {
        int m=1<<(j-1);
        for(int i=0;i<h;i++)
        {
            if(i+m>h-1)
                continue;
            sparce[0][1][i][j]=max(sparce[0][1][i+m][j-1],sparce[0][1][i][j-1]);
        }
    }
    for(int i=0;i<w;i++)
        scanf("%i",&ver[i]);
    sparce[1][0][0][0]=-1;
    for(int i=1;i<w;i++)
    {
        sparce[1][0][i][0]=ver[i-1];
    }
    for(int j=1;j<20;j++)
    {
        int m=1<<(j-1);
        for(int i=0;i<w;i++)
        {
            if(i-m<0)
                continue;
            sparce[1][0][i][j]=max(sparce[1][0][i-m][j-1],sparce[1][0][i][j-1]);
        }
    }
    sparce[1][1][w-1][0]=-1;
    for(int i=0;i<w-1;i++)
    {
        sparce[1][1][i][0]=ver[i+1];
    }
    for(int j=1;j<20;j++)
    {
        int m=1<<(j-1);
        for(int i=0;i<w;i++)
        {
            if(i+m>w-1)
                continue;
            sparce[1][1][i][j]=max(sparce[1][1][i+m][j-1],sparce[1][1][i][j-1]);
        }
    }
    for(int i=0;i<q;i++)
    {
        int x,y;
        scanf("%i %i",&x,&y);
        x--;
        y--;
        printf("%i\n",max(calc(x,y,0),calc(x,y,1)));
    }
    return 0;
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&h,&w,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&hor[i]);
         ~~~~~^~~~~~~~~~~~~~
abduction2.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&ver[i]);
         ~~~~~^~~~~~~~~~~~~~
abduction2.cpp:217: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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 7 ms 5648 KB Output is correct
4 Correct 7 ms 5796 KB Output is correct
5 Correct 8 ms 5796 KB Output is correct
6 Correct 6 ms 5828 KB Output is correct
7 Correct 8 ms 5948 KB Output is correct
8 Correct 7 ms 5948 KB Output is correct
9 Correct 7 ms 5948 KB Output is correct
10 Correct 6 ms 5948 KB Output is correct
11 Correct 7 ms 5948 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 7 ms 5648 KB Output is correct
4 Correct 7 ms 5796 KB Output is correct
5 Correct 8 ms 5796 KB Output is correct
6 Correct 6 ms 5828 KB Output is correct
7 Correct 8 ms 5948 KB Output is correct
8 Correct 7 ms 5948 KB Output is correct
9 Correct 7 ms 5948 KB Output is correct
10 Correct 6 ms 5948 KB Output is correct
11 Correct 7 ms 5948 KB Output is correct
12 Correct 18 ms 6620 KB Output is correct
13 Correct 9 ms 6656 KB Output is correct
14 Correct 8 ms 6712 KB Output is correct
15 Correct 9 ms 6896 KB Output is correct
16 Correct 8 ms 6896 KB Output is correct
17 Correct 9 ms 6896 KB Output is correct
18 Correct 9 ms 6920 KB Output is correct
19 Incorrect 9 ms 7088 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 7 ms 5648 KB Output is correct
4 Correct 7 ms 5796 KB Output is correct
5 Correct 8 ms 5796 KB Output is correct
6 Correct 6 ms 5828 KB Output is correct
7 Correct 8 ms 5948 KB Output is correct
8 Correct 7 ms 5948 KB Output is correct
9 Correct 7 ms 5948 KB Output is correct
10 Correct 6 ms 5948 KB Output is correct
11 Correct 7 ms 5948 KB Output is correct
12 Correct 18 ms 6620 KB Output is correct
13 Correct 9 ms 6656 KB Output is correct
14 Correct 8 ms 6712 KB Output is correct
15 Correct 9 ms 6896 KB Output is correct
16 Correct 8 ms 6896 KB Output is correct
17 Correct 9 ms 6896 KB Output is correct
18 Correct 9 ms 6920 KB Output is correct
19 Incorrect 9 ms 7088 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5624 KB Output is correct
2 Correct 7 ms 5624 KB Output is correct
3 Correct 7 ms 5648 KB Output is correct
4 Correct 7 ms 5796 KB Output is correct
5 Correct 8 ms 5796 KB Output is correct
6 Correct 6 ms 5828 KB Output is correct
7 Correct 8 ms 5948 KB Output is correct
8 Correct 7 ms 5948 KB Output is correct
9 Correct 7 ms 5948 KB Output is correct
10 Correct 6 ms 5948 KB Output is correct
11 Correct 7 ms 5948 KB Output is correct
12 Correct 18 ms 6620 KB Output is correct
13 Correct 9 ms 6656 KB Output is correct
14 Correct 8 ms 6712 KB Output is correct
15 Correct 9 ms 6896 KB Output is correct
16 Correct 8 ms 6896 KB Output is correct
17 Correct 9 ms 6896 KB Output is correct
18 Correct 9 ms 6920 KB Output is correct
19 Incorrect 9 ms 7088 KB Output isn't correct
20 Halted 0 ms 0 KB -