QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#867059	#4356. Giraffes	Zbyszek99	32	6113ms	9164kb	C++14	6.4kb	2025-01-23 01:50:36	2025-01-23 01:50:36

Judging History

你现在查看的是最新测评结果

[2025-01-23 01:50:36]
评测

测评结果：32
用时：6113ms
内存：9164kb

查看

[2025-01-23 01:50:36]
提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int tree_siz = (1 << 15)-1;
int drzewo[tree_siz];

int get_max(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return -1e5;
    if(p1 >= s1 && p2 <= s2) return drzewo[akt-1];
    return max(get_max(akt*2,p1,(p1+p2)/2,s1,s2),get_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}

void upd(int v)
{
    drzewo[v-1]= max(drzewo[v*2-1],drzewo[v*2]);
    if(v != 1) upd(v/2);
}

void change(int ind, int x)
{
    drzewo[tree_siz/2+ind] = x;
    upd((tree_siz/2+ind+1)/2);
}

struct event
{
    int sort_poz, poz, val, ind, type;
    bool operator<(const event& e)
    {
        if(sort_poz != e.sort_poz) return sort_poz < e.sort_poz;
        if(poz != e.poz) return poz < e.poz;
        return type < e.type;
    }
};

pii rotateP(pii point)
{
    return {-point.ss,point.ff};
}

struct square
{
    vector<pii> points;
    square(pii corner, int len)
    {
        points.pb(corner);
        points.pb({corner.ff,corner.ss-len});
        points.pb({corner.ff-len,corner.ss-len});
        points.pb({corner.ff-len,corner.ss});
    }
    void rotate()
    {
        rep(i,4) points[i] = rotateP(points[i]);
        swap(points[0],points[1]);
        swap(points[1],points[2]);
        swap(points[2],points[3]);
    }
};

vector<square> squ;
vector<square> new_squ;
vector<pii> vp;
int min_side[100000];


int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    rep(i,tree_siz) drzewo[i] = -1e5;
    int n;
    cin >> n;
    rep2(i,1,n)
    {
        int x;
        cin >> x;
        square new_s({i,x},0);
        new_squ.pb(new_s);
        vp.pb({i,x});
    }
    int ans = n;
    vector<event> events;
    while(!new_squ.empty())
    {
        ans--;
        swap(new_squ,squ);
        new_squ = {};
       // cout << ans << " iter:\n\nsqu:\n";
       // forall(it,squ)
      //  {
      //      cout << it.points[0].ff << " " << it.points[0].ss << " " << it.points[0].ss - it.points[1].ss << " squ\n";
       // }
        rep(ang,4)
        {
            events = {};
            rep(i,siz(squ))
            {
                events.pb({squ[i].points[0].ss - squ[i].points[0].ff,squ[i].points[0].ff+n,squ[i].points[1].ss,i,1});
            }
            rep(i,n)
            {
                min_side[i] = 1e9;
                events.pb({vp[i].ss-vp[i].ff,vp[i].ff+n,-1,i,0});
            }
            sort(all(events));
            forall(it,events)
            {
                if(it.type == 1)
                {
                 //   cout << it.poz << " " << it.val << " val\n";
                    change(it.poz,it.val);
                }
                else
                {
                    int m = get_max(1,0,tree_siz/2,0,it.poz-1);
                  //  cout << it.ind << " " << it.poz << " ans2\n";
                    min_side[it.ind] = min(min_side[it.ind],vp[it.ind].ss - m);
                }
          //      cout << it.ind << " first\n";
            }
            forall(it,events)
            {
                change(it.poz,-1e5);
            }
            events = {};
            rep(i,siz(squ))
            {
                events.pb({-(squ[i].points[0].ss - squ[i].points[0].ff),squ[i].points[0].ss+n,squ[i].points[2].ff,i,1});
            }
            rep(i,n)
            {
                events.pb({-(vp[i].ss-vp[i].ff),vp[i].ss+n,-1,i,0});
            }
            sort(all(events));
            forall(it,events)
            {
                if(it.type == 1)
                {
                    change(it.poz,it.val);
                }
                else
                {
                    
                    int m = get_max(1,0,tree_siz/2,0,it.poz-1);
                  //  cout << it.ind << " " << m << " ans2\n";
                    min_side[it.ind] = min(min_side[it.ind],vp[it.ind].ff - m);
                }
            //    cout << it.ind << " second\n";
            }
            forall(it,events)
            {
                change(it.poz,-1e5);
            }
            rep(i,n)
            {
              //  cout << min_side[i] << " " << ang << " " << i << " " << vp[i].ff << " " << vp[i].ss << " min_side\n";
                if(min_side[i] <= 10000)
                {
                    square new_s(vp[i],min_side[i]);
                    new_squ.pb(new_s);
                }
            }

            rep(i,n)
            {
                vp[i] = rotateP(vp[i]);
            }
            rep(i,siz(new_squ))
            {
                new_squ[i].rotate();
            }
            rep(i,siz(squ))
            {
                squ[i].rotate();
            }
           // cout << "\nnew angle\n";
        }
     //   cout << " new_squ:\n";
        squ = {};
        forall(it,new_squ)
        {
            
            bool is_ok = true;
            forall(it2,it.points)
            {
                if(it2.ff < 1 || it2.ff > n) is_ok = false;
                if(it2.ss < 1 || it2.ss > n) is_ok = false;
            }
            if(is_ok) 
            {
                squ.pb(it);
              //  cout << it.points[0].ff << " " << it.points[0].ss << " " << it.points[0].ss - it.points[1].ss << " new_squ\n";
            }
        }
        new_squ = squ;
       // if(ans == 5) break;
    }
    cout << ans << "\n";
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 0ms

memory: 3712kb

input:

1
1

output:

result:

ok single line: '0'

Test #2:

score: 10

Accepted

time: 0ms

memory: 3712kb

input:

2
2 1

output:

result:

ok single line: '0'

Test #3:

score: 10

Accepted

time: 1ms

memory: 3712kb

input:

3
1 2 3

output:

result:

ok single line: '0'

Test #4:

score: 10

Accepted

time: 0ms

memory: 3712kb

input:

4
3 1 4 2

output:

result:

ok single line: '2'

Test #5:

score: 10

Accepted

time: 1ms

memory: 3712kb

input:

5
3 4 5 1 2

output:

result:

ok single line: '2'

Test #6:

score: 10

Accepted

time: 0ms

memory: 3712kb

input:

6
1 5 6 2 4 3

output:

result:

ok single line: '2'

Test #7:

score: 10

Accepted

time: 1ms

memory: 3840kb

input:

6
1 6 3 4 2 5

output:

result:

ok single line: '0'

Test #8:

score: 10

Accepted

time: 1ms

memory: 3840kb

input:

7
5 3 4 6 2 7 1

output:

result:

ok single line: '0'

Test #9:

score: 10

Accepted

time: 1ms

memory: 3712kb

input:

7
5 3 7 1 2 6 4

output:

result:

ok single line: '3'

Test #10:

score: 10

Accepted

time: 1ms

memory: 3584kb

input:

7
5 2 3 6 7 1 4

output:

result:

ok single line: '2'

Subtask #2:

score: 22

Accepted

Test #11:

score: 22

Accepted

time: 1ms

memory: 3712kb

input:

8
7 2 1 8 3 5 4 6

output:

result:

ok single line: '3'

Test #12:

score: 22

Accepted

time: 0ms

memory: 3712kb

input:

9
3 1 5 6 8 4 7 9 2

output:

result:

ok single line: '3'

Test #13:

score: 22

Accepted

time: 1ms

memory: 3712kb

input:

10
4 6 5 7 1 2 3 8 9 10

output:

result:

ok single line: '2'

Test #14:

score: 22

Accepted

time: 0ms

memory: 3712kb

input:

11
2 10 3 11 1 5 8 6 4 7 9

output:

result:

ok single line: '5'

Test #15:

score: 22

Accepted

time: 1ms

memory: 3712kb

input:

12
2 7 3 1 9 4 8 12 11 6 5 10

output:

result:

ok single line: '5'

Test #16:

score: 22

Accepted

time: 1ms

memory: 3712kb

input:

12
11 7 4 10 8 3 1 9 12 6 5 2

output:

result:

ok single line: '5'

Test #17:

score: 22

Accepted

time: 1ms

memory: 3840kb

input:

13
11 4 8 5 9 2 3 7 13 12 1 10 6

output:

result:

ok single line: '7'

Test #18:

score: 22

Accepted

time: 1ms

memory: 3840kb

input:

13
6 3 10 8 13 11 4 1 7 5 12 9 2

output:

result:

ok single line: '7'

Test #19:

score: 22

Accepted

time: 0ms

memory: 3712kb

input:

13
11 4 8 2 7 6 5 12 10 1 13 9 3

output:

result:

ok single line: '5'

Test #20:

score: 22

Accepted

time: 1ms

memory: 3712kb

input:

13
4 2 6 7 11 5 3 9 10 1 8 13 12

output:

result:

ok single line: '6'

Subtask #3:

score: 0

Wrong Answer

Test #21:

score: 27

Accepted

time: 1ms

memory: 3712kb

input:

29
7 22 11 16 27 1 24 12 6 21 13 2 10 8 25 15 4 19 17 9 23 5 14 20 18 28 26 29 3

output:

result:

ok single line: '17'

Test #22:

score: 27

Accepted

time: 5ms

memory: 3712kb

input:

96
80 30 84 26 53 63 96 48 15 40 35 10 81 68 55 57 25 2 41 56 64 65 42 74 93 69 58 32 21 85 14 79 22 38 51 8 5 27 19 20 16 94 31 23 86 36 17 77 75 62 12 87 71 76 11 13 52 44 45 4 46 60 54 3 73 70 72 66 67 92 88 59 61 7 34 89 24 49 18 37 28 91 47 1 90 9 95 82 83 33 29 78 50 6 43 39

output:

result:

ok single line: '73'

Test #23:

score: 27

Accepted

time: 14ms

memory: 3840kb

input:

185
152 65 146 109 33 14 44 141 174 154 37 11 177 39 82 58 70 36 81 163 76 98 20 182 129 142 64 5 126 91 25 55 42 105 173 155 121 96 50 102 178 66 22 168 99 7 115 183 27 95 93 23 3 181 106 84 89 171 18 148 156 41 162 47 139 112 86 35 97 134 12 77 160 13 34 118 104 111 15 2 46 51 136 87 110 145 71 15...

output:

result:

ok single line: '151'

Test #24:

score: 0

Wrong Answer

time: 21ms

memory: 3968kb

input:

242
3 137 21 188 170 212 192 186 122 144 165 43 27 109 156 52 108 222 98 151 155 228 183 124 7 17 26 217 68 82 229 1 169 92 47 206 29 145 149 241 185 196 99 44 67 51 139 153 141 128 73 104 142 219 119 50 36 161 178 18 11 193 54 107 70 102 49 103 20 13 78 9 59 40 63 30 31 12 159 45 234 60 69 225 242 ...

output:

result:

wrong answer 1st lines differ - expected: '202', found: '203'

Subtask #4:

score: 0

Wrong Answer

Test #31:

score: 41

Accepted

time: 845ms

memory: 5056kb

input:

2317
1841 533 998 38 1358 1204 1174 176 581 1719 550 906 35 101 442 1068 1781 601 1368 2190 2095 919 2186 1134 1814 625 90 2007 653 186 204 997 1607 1675 45 806 483 299 27 935 1070 1425 1822 1712 2074 2259 264 840 1960 1045 1742 1185 577 142 980 151 2136 2143 955 462 1373 395 1300 185 637 734 803 13...

output:

result:

ok single line: '2188'

Test #32:

score: 41

Accepted

time: 3641ms

memory: 7352kb

input:

5832
1722 2970 5519 3937 611 905 5560 3982 2598 4702 1508 3021 4042 2233 2271 4583 1554 1867 1640 2659 2580 1468 413 2708 533 4008 5152 3074 2466 1521 5101 1797 5453 702 25 3750 1781 1598 1755 2091 1894 786 3591 4058 5088 5307 2926 2222 1708 256 1249 1815 5505 3273 2016 4315 1161 2376 5409 612 1157 ...

output:

result:

ok single line: '5626'

Test #33:

score: 41

Accepted

time: 6016ms

memory: 8628kb

input:

7993
444 5307 3841 3057 5739 487 4824 7828 1189 692 1095 1529 2503 1401 6936 3688 5934 3393 7793 1068 4160 1109 4933 3844 3137 6057 4296 825 5432 2159 3365 1819 7530 4753 463 6298 1029 5558 3398 5323 1448 2120 23 913 2592 3758 2740 5811 5295 7460 3068 37 3075 5838 7248 7348 2019 5679 7261 5176 5235 ...

output:

result:

ok single line: '7748'

Test #34:

score: 41

Accepted

time: 6020ms

memory: 8792kb

input:

7994
3179 1801 4177 2524 5297 7481 3410 4287 7420 7465 6657 7229 5939 2570 3316 286 1989 7006 2015 6818 7717 4004 1929 2486 2201 4352 791 714 3435 5766 773 1836 7130 7662 5885 6424 7538 2098 471 1563 677 2738 1525 728 5740 3412 5416 4808 2773 2449 1765 41 6811 1990 2511 4540 4908 2971 3361 6863 3466...

output:

result:

ok single line: '7753'

Test #35:

score: 41

Accepted

time: 6025ms

memory: 8612kb

input:

7995
298 3649 6679 293 2589 5476 6327 7299 5804 5311 4672 1238 3698 5027 4219 3496 5409 2987 1466 5799 2031 7653 1172 7424 3645 5625 6568 2157 3030 5177 1492 7478 6644 4286 1612 59 6805 3222 6703 4742 2719 5626 6320 3381 4450 6429 661 3172 2735 2267 6581 6286 7640 2440 2784 341 637 2245 7874 121 183...

output:

result:

ok single line: '7752'

Test #36:

score: 41

Accepted

time: 6015ms

memory: 8796kb

input:

7996
5467 6280 6464 790 428 3075 1210 1770 2052 4187 5648 6981 7057 2971 558 2173 3654 5366 2136 6972 286 2190 4444 1578 2990 2043 5972 5748 6749 1389 7236 2776 134 1806 7567 226 3381 3995 1275 7043 745 7068 1766 5953 6379 3653 4273 1633 4817 1439 3432 3390 1936 3010 1370 3606 4519 599 4778 3249 321...

output:

result:

ok single line: '7752'

Test #37:

score: 41

Accepted

time: 6097ms

memory: 8800kb

input:

7997
3305 3912 6210 2988 7049 5003 5690 59 712 7974 4251 6767 2679 5824 1317 6904 5581 5875 1938 1811 810 5241 4868 2551 7581 602 2797 2148 6639 6786 7881 627 1349 6128 2314 167 3245 1215 6694 4965 4165 2708 7702 3543 4453 4787 5361 1249 6107 3777 4955 5615 6159 7275 2707 7624 6284 1104 7826 5339 39...

output:

result:

ok single line: '7754'

Test #38:

score: 0

Wrong Answer

time: 6113ms

memory: 9164kb

input:

7998
2737 7370 3290 6547 2700 4011 6863 6031 3274 3849 7364 1162 4026 1676 7609 7340 2121 6747 2398 5962 5456 4196 2838 6376 977 2659 6589 365 839 7391 7906 3250 4234 1056 2539 1236 5449 6912 1217 3129 207 5856 5566 5184 7125 4331 53 6331 7772 2559 5830 6791 4743 6438 7928 4826 1001 1008 3161 1340 2...

output:

result:

wrong answer 1st lines differ - expected: '7751', found: '7752'