Submission #1689355
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
#define datatype int
#define inf (int)(1e9 + 7)
datatype min(datatype a, datatype b){
if(a < b){
return a;
}
else{
return b;
}
}
datatype sum(datatype a, datatype b){
if(a >= inf || b >= inf){
return inf;
}
else{
return a + b;
}
}
datatype rep_min(datatype a, int N){
return a;
}
int malloc_count = 0;
typedef struct node_sub{
int N; //ノードが含む範囲(2の冪)
datatype val; //値
datatype arg1; //更新操作の第1引数
datatype arg2; //更新操作の第2引数
struct node_sub *left; //左の子, [0, N / 2)を含む
struct node_sub *right; //右の子, [N / 2, N)を含む
}node; //ノード
typedef struct {
node *root; //最も範囲が広いノードへのポインタ
datatype e0; //和の単位元
datatype e1; //積の単位元
datatype (*sum)(datatype x, datatype y); //和の演算
datatype (*pro)(datatype x, datatype y); //積の演算
datatype (*rep_sum)(datatype x, int N); //和の冪演算
}segment_tree;
//ノードrの更新引数を更新する
void argument_update(node *r, datatype arg1, datatype arg2, segment_tree *t){
r->arg2 = (t->sum)((t->pro)(arg1, r->arg2), arg2);
r->arg1 = (t->pro)(arg1, r->arg1);
}
//範囲がNのノードを生成する
node *make_node(int N, segment_tree *t){
malloc_count++;
node *r = (node *)malloc(sizeof(node));
r->N = N;
r->val = t->e0;
r->arg1 = t->e1;
r->arg2 = t->e0;
r->left = NULL;
r->right = NULL;
return r;
}
//ノードrの中身を出力する
void out_node(node *r){
printf("N = %d\n", r->N);
printf("val = %d\n", r->val);
printf("arg1 = %d\n", r->arg1);
printf("arg2 = %d\n", r->arg2);
if(r->left == NULL && r->right == NULL){
printf("no_children\n");
}
else{
printf("have_children\n");
}
printf("\n");
}
//ノードの(遅延していない)真の値を返す
datatype true_val(node *r, segment_tree *t){
return (t->sum)((t->pro)(r->arg1, r->val), (t->rep_sum)(r->arg2, r->N));
}
//ノードの更新操作を子(いなければ作る)に伝播する
//自ノードの遅延は解消する
void propagate(node *r, segment_tree *t){
if(r->N > 1){
if(r->left == NULL && r->right == NULL){
r->left = make_node(r->N / 2, t);
r->right = make_node(r->N / 2, t);
}
if(r->arg1 != t->e1 || r->arg2 != t->e0){
argument_update(r->left, r->arg1, r->arg2, t);
argument_update(r->right, r->arg1, r->arg2, t);
r->val = true_val(r, t);
r->arg1 = t->e1;
r->arg2 = t->e0;
}
}
else if(r->arg1 != t->e1 || r->arg2 != t->e0){
r->val = true_val(r, t);
r->arg1 = t->e1;
r->arg2 = t->e0;
}
}
//nを越える最小の2冪を返す
int next_exponent_of_2(int n){
if(n == 0){
return 1;
}
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
// n |= (n >> 32); //long longの時
return (n << 1) ^ n - 1;
}
void update_sub(int a, int b, datatype arg1, datatype arg2, node *r, segment_tree *t){
if(r->N <= a || b <= 0){
return;
}
else if(a <= 0 && r->N <= b){
argument_update(r, arg1, arg2, t);
}
else{
propagate(r, t);
update_sub(a, b, arg1, arg2, r->left, t);
update_sub(a - r->N / 2, b - r->N / 2, arg1, arg2, r->right, t);
r->val = (t->sum)(true_val(r->left, t), true_val(r->right, t));
}
}
datatype query_sub(int a, int b, node *r, segment_tree *t){
if(r->N <= a || b <= 0){
return t->e0;
}
else if(a <= 0 && r->N <= b){
return true_val(r, t);
}
else if(r->left == NULL && r->right == NULL){
return (t->rep_sum)(r->arg2, (b < r->N ? b : r->N) - (0 < a ? a : 0));
}
else{
propagate(r, t);
return (t->sum)(query_sub(a, b, r->left, t), query_sub(a - r->N / 2, b - r->N / 2, r->right, t));
}
}
//和の単位元e0
//積の単位元e1
//和の演算sum
//積の演算pro
//和の冪演算rep_sum
//のsegment_treeを生成する
//ただし, datatypeが環になっている必要がある
//すなわち,
//datatypeは和に関してアーベル群(結合律の成立, 単位元の存在, 逆元の存在, 可換性の成立)
//datatypeは積に関してモノイド(結合律の成立, 単位元の存在)
//分配律の成立
//を全て満たす必要がある
segment_tree *make_segment_tree(datatype e0, datatype e1, datatype (*sum)(datatype x, datatype y), datatype (*pro)(datatype x, datatype y), datatype (*rep_sum)(datatype x, int N)){
segment_tree *t = (segment_tree *)malloc(sizeof(segment_tree));
t->root = NULL;
t->e0 = e0;
t->e1 = e1;
t->sum = sum;
t->pro = pro;
t->rep_sum = rep_sum;
return t;
}
//[a, b)の範囲に引数がarg1, arg2の線形更新操作を施す
//arg1に和の単位元を入れると範囲内の各要素にarg2を代入する
//arg1に積の単位元を入れると範囲内の各要素でarg2との和を取る
void update(int a, int b, datatype arg1, datatype arg2, segment_tree *t){
if(t->root == NULL){
t->root = make_node(next_exponent_of_2(b - 1), t);
}
else if(t->root->N < b){
node *r = make_node(2 * t->root->N, t);
r->val = true_val(t->root, t);
r->left = t->root;
r->right = make_node(r->left->N, t);
t->root = r;
update(a, b, arg1, arg2, t);
return;
}
update_sub(a, b, arg1, arg2, t->root, t);
}
//[a, b)の範囲の和の結果を返す
datatype query(int a, int b, segment_tree *t){
if(t->root == NULL){
return t->e0;
}
else{
return query_sub(a, b, t->root, t);
}
}
int main(){
int N, M, i, k = 0;
scanf("%d%d", &N, &M);
segment_tree *seg_t = make_segment_tree(inf, 0, min, sum, rep_min);
update(1, N + 1, 0, 0, seg_t);
int *s = (int *)malloc(sizeof(int) * M);
int *t = (int *)malloc(sizeof(int) * M);
for(i = 0; i < M; i++){
scanf("%d%d", &s[i], &t[i]);
update(s[i], t[i] + 1, 1, inf, seg_t);
}
/* printf("test:\n");
for(i = 1; i <= N; i++){
printf("%d\n", query(i, i + 1, seg_t));
}
printf("\n");
*/ int *ans = (int *)malloc(sizeof(int) * M);
for(i = 0; i < M; i++){
if(query(s[i], t[i] + 1, seg_t) > 1){
ans[k] = i + 1;
k++;
}
}
printf("%d\n", k);
for(i = 0; i < k; i++){
printf("%d\n", ans[i]);
}
return 0;
}
Submission Info
Submission Time
2017-10-17 00:02:52+0900
Task
B - ドキドキデート大作戦高橋君
User
abc050
Language
C (GCC 5.4.1)
Score
100
Code Size
6248 Byte
Status
AC
Exec Time
291 ms
Memory
20608 KB
Compile Error
./Main.c: In function ‘main’:
./Main.c:212:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
^
./Main.c:218:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &s[i], &t[i]);
^
Judge Result
Set Name
Sample
Subtask1
All
Score / Max Score
0 / 0
30 / 30
70 / 70
Status
Set Name
Test Cases
Sample
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Case Name
Status
Exec Time
Memory
subtask0_sample_01.txt
AC
1 ms
128 KB
subtask0_sample_02.txt
AC
1 ms
128 KB
subtask0_sample_03.txt
AC
1 ms
128 KB
subtask1_01.txt
AC
123 ms
19712 KB
subtask1_02.txt
AC
137 ms
18304 KB
subtask1_03.txt
AC
112 ms
14976 KB
subtask1_04.txt
AC
145 ms
13440 KB
subtask1_05.txt
AC
145 ms
13440 KB
subtask1_06.txt
AC
1 ms
128 KB
subtask1_07.txt
AC
1 ms
128 KB
subtask1_08.txt
AC
1 ms
128 KB
subtask1_09.txt
AC
1 ms
128 KB
subtask2_01.txt
AC
190 ms
1920 KB
subtask2_02.txt
AC
203 ms
20608 KB
subtask2_03.txt
AC
1 ms
128 KB
subtask2_04.txt
AC
1 ms
128 KB
subtask2_05.txt
AC
1 ms
128 KB
subtask2_06.txt
AC
1 ms
128 KB
subtask2_07.txt
AC
1 ms
128 KB
subtask2_08.txt
AC
291 ms
17920 KB