Submission #300897

# Submission time Handle Problem Language Result Execution time Memory
300897 2020-09-17T14:53:55 Z CodePlatina Comparing Plants (IOI20_plants) C++14
0 / 100
73 ms 3320 KB
#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

struct Node
{
    pii mn, lazy;
}seg[808080];

void prop(int ind)
{
    Node &x = seg[ind << 1], &y = seg[ind << 1 | 1], &nd = seg[ind];
    if(nd.lazy.ff)
    {
        x.mn.ff += nd.lazy.ff;
        y.mn.ff += nd.lazy.ff;
        x.lazy.ff += nd.lazy.ff;
        y.lazy.ff += nd.lazy.ff;
        nd.lazy.ff = 0;
    }
    if(nd.lazy.ss)
    {
        x.mn.ss += nd.lazy.ss;
        y.mn.ss += nd.lazy.ss;
        x.lazy.ss += nd.lazy.ss;
        y.lazy.ss += nd.lazy.ss;
        nd.lazy.ss = 0;
    }
}

void mrge(int ind)
{
    seg[ind].mn = min(seg[ind << 1].mn, seg[ind << 1 | 1].mn);
}

void init_seg(vector<int> &r, int ind, int s, int e)
{
    if(s + 1 == e)
    {
        seg[ind].mn = {r[s], 0};
        seg[ind].lazy = {0, 0};
        return;
    }

    int mid = s + e >> 1;
    init_seg(r, ind << 1, s, mid);
    init_seg(r, ind << 1 | 1, mid, e);
    mrge(ind);
}

void upd1(int ind, int s, int e, int l, int r, int x)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        seg[ind].mn.ff += x;
        seg[ind].lazy.ff += x;
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    upd1(ind << 1, s, mid, l, r, x);
    upd1(ind << 1 | 1, mid, e, l, r, x);
    mrge(ind);
}

void upd2(int ind, int s, int e, int l, int r)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        ++seg[ind].mn.ss;
        ++seg[ind].lazy.ss;
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    upd2(ind << 1, s, mid, l, r);
    upd2(ind << 1 | 1, mid, e, l, r);
    mrge(ind);
}

void qr1(vector<int> &ret, int ind, int s, int e, int l, int r)
{
    if(e <= l || r <= s || seg[ind].mn.ff) return;
    if(s + 1 == e)
    {
        ret.push_back(s);
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    qr1(ret, ind << 1, s, mid, l, r);
    qr1(ret, ind << 1 | 1, mid, e, l, r);
}

int qr2(int ind, int s, int e)
{
    if(s + 1 == e) return s;

    prop(ind);
    int mid = s + e >> 1;
    if(seg[ind << 1].mn == pii{0, 0}) return qr2(ind << 1, s, mid);
    else return qr2(ind << 1 | 1, mid, e);
}

int N, K;
int ord[202020];

void init(int k, vector<int> r)
{
	N = r.size(); K = k;
	init_seg(r, 1, 0, N);

	for(int i = 0; i < N; ++i)
    {
        int t = qr2(1, 0, N);
        ord[t] = i;

        vector<int> ls;
        if(t >= K - 1)
        {
            upd1(1, 0, N, t - K + 1, t, -1);
            upd1(1, 0, N, t, t + 1, N);
            qr1(ls, 1, 0, N, t - K + 1, t);
        }
        else
        {
            upd1(1, 0, N, 0, t, -1);
            upd1(1, 0, N, N - K + t + 1, N, -1);
            upd1(1, 0, N, t, t + 1, N);
            qr1(ls, 1, 0, N, 0, t);
            qr1(ls, 1, 0, N, N - K + t + 1, N);
        }

        for(int j : ls)
        {
            if(j <= N - K) upd2(1, 0, N, j + 1, j + K);
            else
            {
                upd2(1, 0, N, j + 1, N);
                upd2(1, 0, N, 0, K - N + j);
            }
        }
    }

//    for(int i = 0; i < N; ++i)
//    {
//        for(int j = 0; j < N; ++j)
//        {
//            for(int k = 0; k < N; ++k)
//            {
//                if(arr[j][i] && arr[i][k]) arr[j][k] = true;
//            }
//        }
//    }

//    for(int i = 0; i < N; ++i)
//    {
//        for(int j = 0; j < N; ++j)
//        {
//            cout << arr[i][j];
//        }
//        cout << endl;
//    }
}

int compare_plants(int x, int y)
{
	if(ord[x] < ord[y]) return 1;
	else return -1;
}

Compilation message

plants.cpp: In function 'void init_seg(std::vector<int>&, int, int, int)':
plants.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd1(int, int, int, int, int, int)':
plants.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void upd2(int, int, int, int, int)':
plants.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'void qr1(std::vector<int>&, int, int, int, int, int)':
plants.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     int mid = s + e >> 1;
      |               ~~^~~
plants.cpp: In function 'int qr2(int, int, int)':
plants.cpp:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |     int mid = s + e >> 1;
      |               ~~^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 73 ms 3320 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -