我就讨厌这样的刷题网站,用于判断的那个程序完全知道 输入数据、正确答案、你程序给出的答案
但是这个程序是这样说的,你写的这个程序不对,至于有什么问题,我不告诉你,你自己去看代码,改代码
一个好的刷题网站应该是这样的
你的这个程序不正确,在输入 1234 的时候,正确的输出应该是 1,但是你提供的程序输出的是 0
你看这样不好吗?有了输入数据、正确答案、错误答案,可以非常快速的定位代码中存在的问题
对于前面的那个刷题网站,他不告诉我这 3 个数据,我只能一行代码一行代码的找问题,想了又想,是哪里漏掉了某种情况?
我非常非常讨厌这样的刷题网站,因为代码出现问题根本没法修改代码,因为不知道这 3 个数据,输入数据、正确答案、错误答案
好了,下面说正事
再试一下这个代码,这次用了 线段树(大概,^_^)
segment_tree.hpp#ifndef _SEGMENT_TREE_HPP_
#define _SEGMENT_TREE_HPP_
#include <cstddef>
template <typename T>
class segment_tree_t {
public:
segment_tree_t(size_t begin, size_t end, T value = T()): root(nullptr) {
if(begin > end) return;
root = create(begin, end, value);
}
~segment_tree_t() {
free(root);
}
bool get(size_t begin, size_t end, long long &sum) {
if(!root) return false;
if(begin > end) return false;
sum = get_sub(root, begin, end);
return true;
}
bool set(size_t begin, size_t end, T value) {
if(!root) return false;
if(begin > end) return false;
set_sub(root, begin, end, value);
return true;
}
private:
struct node_t {
size_t begin, end;
T value;
node_t *lchrild, *rchrild;
};
node_t *root;
static node_t *create(size_t begin, size_t end, T value) {
node_t *root = new node_t();
root->begin = begin;
root->end = end;
if(begin == end) {
root->lchrild = root->rchrild = nullptr;
root->value = value;
return root;
}
size_t middle = (begin + end) / 2;
root->lchrild = create(begin, middle, value);
root->rchrild = create(middle + 1, end, value);
root->value = root->lchrild->value + root->rchrild->value;
return root;
}
static void free(node_t *root) {
if(!root) return;
free(root->lchrild);
free(root->rchrild);
delete root;
}
static long long get_sub(node_t *root, size_t begin, size_t end) {
if(root->begin > end || root->end < begin) return 0;
if(root->begin >= begin && root->end <= end) return root->value;
return get_sub(root->lchrild, begin, end) + get_sub(root->rchrild, begin, end);
}
static void set_sub(node_t *root, size_t begin, size_t end, T value) {
if(root->begin > end || root->end < begin) return;
if(root->begin == root->end) {root->value = value; return;}
set_sub(root->lchrild, begin, end, value);
set_sub(root->rchrild, begin, end, value);
root->value = root->lchrild->value + root->rchrild->value;
}
segment_tree_t(const segment_tree_t &rhs) = delete;
segment_tree_t &operator=(const segment_tree_t &rhs) = delete;
};
#endif
main.cpp#include <iostream>
#include "segment_tree.hpp"
int main() {
size_t n, m; std::cin >> n >> m;
segment_tree_t<size_t> st(1, m);
for(size_t i = 0; i < n; ++i) {
size_t l, r; std::cin >> l >> r;
long long sum;
st.get(l, r, sum);
if(sum == 0) {
st.set(l, r, 1);
std::cout << "ACCEPTED" << std::endl;
} else std::cout << "REJECTED" << std::endl;
}
return 0;
}
|