oj.uz

Submission #429619

# Submission time Handle Problem Language Result Execution time Memory
429619 2021-06-16T07:49:41 Z Amylopectin Wall (IOI14_wall) C++14
100 / 100
 963 ms 77332 KB 
#include <iostream>
#include <stdio.h>
#include "wall.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 8e6 + 10,mxi = 1e7 + 10;
struct we
{
    int bb,ub;
};
struct we se[mxn] = {};
int ban[mxn] = {};
int fimi(int l,int r)
{
    if(l < r)
        return l;
    return r;
}
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int cre(int cl,int cr,int no)
{
    if(cl == cr)
    {
        se[no] = {0,0};
        return 0;
    }
    int mid = (cl+cr) / 2;
    se[no] = {0,mxi};
    cre(cl,mid,no*2);
    cre(mid+1,cr,no*2+1);
    return 0;
}
int ins(int cl,int cr,int no,int tl,int tr,int iva,int uob,int dob,int dou)
{
    if(cr < tl || cl > tr)
    {
        if(dob > se[no].ub)
        {
            se[no].bb = dob;
            se[no].ub = dob;
        }
        else if(dou < se[no].bb)
        {
            se[no].bb = dou;
            se[no].ub = dou;
        }
        else
        {
            se[no].bb = fima(dob,se[no].bb);
            se[no].ub = fimi(dou,se[no].ub);
        }
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        if(dob > se[no].ub)
        {
            se[no].bb = dob;
            se[no].ub = dob;
        }
        else if(dou < se[no].bb)
        {
            se[no].bb = dou;
            se[no].ub = dou;
        }
        else
        {
            se[no].bb = fima(dob,se[no].bb);
            se[no].ub = fimi(dou,se[no].ub);
        }
//        se[no].bb = fima(dob,se[no].bb);
//        se[no].ub = fimi(dou,se[no].ub);
        if(uob == 1)
        {
            if(iva > se[no].ub)
            {
                se[no].bb = iva;
                se[no].ub = iva;
            }
            else
            {
                se[no].bb = fima(iva,se[no].bb);
            }
        }
        else
        {
            if(iva < se[no].bb)
            {
                se[no].bb = iva;
                se[no].ub = iva;
            }
            else
            {
                se[no].ub = fimi(iva,se[no].ub);
            }
        }
        return 0;
    }
    int mid = (cl+cr) / 2;
    if(dob > se[no].ub)
    {
        dou = dob;
    }
    else if(dou < se[no].bb)
    {
        dob = dou;
    }
    else
    {
        dob = fima(dob,se[no].bb);
        dou = fimi(dou,se[no].ub);
    }
    se[no].bb = 0;
    se[no].ub = mxi;
    ins(cl,mid,no*2,tl,tr,iva,uob,dob,dou);
    ins(mid+1,cr,no*2+1,tl,tr,iva,uob,dob,dou);
    return 0;
}
int las(int cl,int cr,int no,int dob,int dou)
{
    if(cl == cr)
    {
        if(dob > se[no].ub)
        {
            se[no].bb = dob;
            se[no].ub = dob;
        }
        else if(dou < se[no].bb)
        {
            se[no].bb = dou;
            se[no].ub = dou;
        }
        else
        {
            se[no].bb = fima(dob,se[no].bb);
            se[no].ub = fimi(dou,se[no].ub);
        }
        ban[cl] = se[no].bb;
        return 0;
    }
    int mid = (cl+cr) / 2;
    if(dob > se[no].ub)
    {
        dou = dob;
    }
    else if(dou < se[no].bb)
    {
        dob = dou;
    }
    else
    {
        dob = fima(dob,se[no].bb);
        dou = fimi(dou,se[no].ub);
    }
    se[no].bb = dob;
    se[no].ub = dou;
    las(cl,mid,no*2,dob,dou);
    las(mid+1,cr,no*2+1,dob,dou);
    return 0;
}
void buildWall(int n, int k, int op[], int le[], int ri[], int ahei[], int ans[])
{
    int i,j;
    cre(0,n-1,1);
    for(i=0; i<k; i++)
    {
        ins(0,n-1,1,le[i],ri[i],ahei[i],op[i],0,mxi);
    }
    las(0,n-1,1,0,mxi);
    for(i=0; i<n; i++)
    {
        ans[i] = ban[i];
    }
    return;
}
//int main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:168:11: warning: unused variable 'j' [-Wunused-variable]
  168 |     int i,j;
      |           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 8 ms 832 KB Output is correct
6 Correct 6 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 205 ms 13904 KB Output is correct
3 Correct 187 ms 7960 KB Output is correct
4 Correct 609 ms 20720 KB Output is correct
5 Correct 376 ms 21800 KB Output is correct
6 Correct 362 ms 20212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 10 ms 768 KB Output is correct
5 Correct 8 ms 764 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 160 ms 13904 KB Output is correct
9 Correct 210 ms 8004 KB Output is correct
10 Correct 607 ms 20716 KB Output is correct
11 Correct 403 ms 21780 KB Output is correct
12 Correct 395 ms 20212 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 165 ms 13880 KB Output is correct
15 Correct 36 ms 2004 KB Output is correct
16 Correct 652 ms 20980 KB Output is correct
17 Correct 405 ms 20448 KB Output is correct
18 Correct 367 ms 20396 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 7 ms 772 KB Output is correct
6 Correct 6 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 156 ms 13968 KB Output is correct
9 Correct 200 ms 8052 KB Output is correct
10 Correct 588 ms 20796 KB Output is correct
11 Correct 400 ms 21780 KB Output is correct
12 Correct 363 ms 20208 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 203 ms 13964 KB Output is correct
15 Correct 39 ms 2008 KB Output is correct
16 Correct 688 ms 20960 KB Output is correct
17 Correct 424 ms 20408 KB Output is correct
18 Correct 369 ms 20480 KB Output is correct
19 Correct 876 ms 77260 KB Output is correct
20 Correct 838 ms 74936 KB Output is correct
21 Correct 858 ms 77284 KB Output is correct
22 Correct 834 ms 74796 KB Output is correct
23 Correct 956 ms 74844 KB Output is correct
24 Correct 836 ms 74836 KB Output is correct
25 Correct 852 ms 74860 KB Output is correct
26 Correct 852 ms 77332 KB Output is correct
27 Correct 858 ms 77284 KB Output is correct
28 Correct 958 ms 74764 KB Output is correct
29 Correct 947 ms 74788 KB Output is correct
30 Correct 963 ms 74856 KB Output is correct