Submission #25504574

Source Code Expand

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long

template <typename T>
void read (T &x) {
    x = 0; T f = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar ();
    }
    x *= f;
}
template <typename T> T Max (T x, T y) { return x > y ? x : y; }

const int Maxn = 2 * 1e5;
const int Inf = 0x3f3f3f3f;

int n, m;

struct sec {
    int l, r, x;
}a[Maxn + 5];
bool cmp (sec x, sec y) {
    return x.r < y.r;
}

struct Node {
    int l, r;
    int Size, idx;
};
#define ls (p << 1)
#define rs (p << 1 | 1)
#define lp (Tr[p].l)
#define rp (Tr[p].r)
#define midp ((lp + rp) >> 1)
#define Sizep (Tr[p].Size)
#define idxp (Tr[p].idx)
struct Segment_Tree {
    Node Tr[(Maxn << 2) + 5];
    
    void Push_Up (int p) {
        Sizep = Tr[ls].Size + Tr[rs].Size;
        idxp = Max (Tr[ls].idx, Tr[rs].idx);
    }
    void Build (int p, int l, int r) {
        lp = l; rp = r;
        if (lp == rp) {
            Sizep = 1; idxp = l;
            return;
        }
        Build (ls, l, midp);
        Build (rs, midp + 1, r);
        Push_Up (p);
    }
    bool Update (int p, int l, int r) {
        if (l <= lp && rp <= r) {
            if (Sizep == 0) return 0;
            if (lp == rp) {
            	Sizep = 0; idxp = -Inf;
            	return 1;
			}
            bool flag = Update (rs, l, r);
            Push_Up (p);
            if (flag == 1) return 1;
            flag = Update (ls, l, r);
            Push_Up (p);
            return flag;
        }
        else if (l <= midp && r > midp) {
            bool flag = Update (rs, l, r);
            Push_Up (p);
            if (flag == 1) return 1;
            flag = Update (ls, l, r);
            Push_Up (p);
            return flag;
        }
        else if (l <= midp) {
            bool flag = Update (ls, l, r);
            Push_Up (p);
            return flag;
        }
        else {
            bool flag = Update (rs, l, r);
            Push_Up (p);
            return flag;
        }
    }
    int Query (int p, int l, int r) {
        if (l <= lp && rp <= r) {
            return Sizep;
        }
        int res = 0;
        if (l <= midp) res += Query (ls, l, r);
        if (r > midp) res += Query (rs, l, r);
        return res;
    }
}Tree;

int main () {
    read (n); read (m);
    for (int i = 1; i <= m; i++) {
        read (a[i].l); read (a[i].r); read (a[i].x);
    }
    sort (a + 1, a + 1 + m, cmp);
    Tree.Build (1, 1, n);
    for (int i = 1; i <= m; i++) {
    	int k = a[i].x - (a[i].r - a[i].l + 1 - Tree.Query (1, a[i].l, a[i].r));
    	if (k < 0) continue;
    	while (k--) {
    		Tree.Update (1, a[i].l, a[i].r);
		}
	}
	for (int i = 1; i <= n; i++) {
		printf ("%d ", Tree.Query (1, i, i) ^ 1);
	}
    return 0;
}

Submission Info

Submission Time
Task G - 01Sequence
User C2022lihan
Language C++ (Clang 10.0.0)
Score 600
Code Size 3076 Byte
Status AC
Exec Time 193 ms
Memory 13732 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 65
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 11 ms 2996 KiB
001.txt AC 9 ms 3216 KiB
002.txt AC 3 ms 3260 KiB
003.txt AC 7 ms 3164 KiB
004.txt AC 3 ms 3144 KiB
005.txt AC 5 ms 3352 KiB
006.txt AC 68 ms 5460 KiB
007.txt AC 67 ms 5420 KiB
008.txt AC 71 ms 5300 KiB
009.txt AC 66 ms 11328 KiB
010.txt AC 69 ms 11028 KiB
011.txt AC 72 ms 11332 KiB
012.txt AC 95 ms 11348 KiB
013.txt AC 98 ms 11212 KiB
014.txt AC 96 ms 11212 KiB
015.txt AC 189 ms 13432 KiB
016.txt AC 188 ms 13428 KiB
017.txt AC 191 ms 13420 KiB
018.txt AC 131 ms 12672 KiB
019.txt AC 126 ms 12708 KiB
020.txt AC 133 ms 12760 KiB
021.txt AC 132 ms 12600 KiB
022.txt AC 8 ms 2900 KiB
023.txt AC 53 ms 11320 KiB
024.txt AC 91 ms 11148 KiB
025.txt AC 56 ms 11056 KiB
026.txt AC 8 ms 2916 KiB
027.txt AC 2 ms 3000 KiB
028.txt AC 42 ms 4636 KiB
029.txt AC 42 ms 4696 KiB
030.txt AC 56 ms 11060 KiB
031.txt AC 56 ms 11088 KiB
032.txt AC 55 ms 11072 KiB
033.txt AC 57 ms 11084 KiB
034.txt AC 56 ms 11188 KiB
035.txt AC 150 ms 13428 KiB
036.txt AC 153 ms 13620 KiB
037.txt AC 150 ms 13596 KiB
038.txt AC 153 ms 13392 KiB
039.txt AC 153 ms 13596 KiB
040.txt AC 95 ms 11284 KiB
041.txt AC 97 ms 11388 KiB
042.txt AC 94 ms 11052 KiB
043.txt AC 98 ms 11092 KiB
044.txt AC 96 ms 11396 KiB
045.txt AC 182 ms 13400 KiB
046.txt AC 182 ms 13392 KiB
047.txt AC 185 ms 13488 KiB
048.txt AC 185 ms 13512 KiB
049.txt AC 185 ms 13436 KiB
050.txt AC 76 ms 11736 KiB
051.txt AC 74 ms 11824 KiB
052.txt AC 72 ms 11620 KiB
053.txt AC 73 ms 11612 KiB
054.txt AC 72 ms 11556 KiB
055.txt AC 132 ms 13492 KiB
056.txt AC 134 ms 13732 KiB
057.txt AC 184 ms 13620 KiB
058.txt AC 185 ms 13436 KiB
059.txt AC 123 ms 13392 KiB
060.txt AC 162 ms 13368 KiB
061.txt AC 139 ms 13596 KiB
062.txt AC 193 ms 13364 KiB
example0.txt AC 6 ms 2984 KiB
example1.txt AC 2 ms 2916 KiB