Submission #828758

#	Time	Username	Problem	Language	Result	Execution time	Memory
828758		dijbkr	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	42 ms	1496 KiB

joi2019_ho_t4

//const int NUMBEROFNODES = ...;
//struct Trie{
//    struct Node{
//        int child[26];
//        int exist, cnt;
//    } nodes[NUMBEROFNODES];
//
//    int cur; // Hiện trong trie đang có bao nhiêu đỉnh
//    Trie() : cur(0) { // Tạo nút gốc cho Trie là đỉnh 0 khi khởi tạo Trie
//        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
//        nodes[0].exist = nodes[0].cnt = 0;
//    };
//
//    int new_node() { // Tạo và trả về giá trị của đỉnh mới được tạo ra
//        cur++;
//        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
//        nodes[cur].exist = nodes[cur].cnt = 0;
//        return cur;
//    }
//
//    void add_string(string s) {
//        int pos = 0;
//        for (auto f : s) {
//            int c = f - 'a';
//            if (nodes[pos].child[c] == -1) { // Nếu cạnh tương ứng chữ cái c
//                                             // chưa tồn tại thì ta tạo ra đỉnh mới
//                nodes[pos].child[c] = new_node();
//            }
//            pos = nodes[pos].child[c];
//            nodes[pos].cnt++; // Có thêm một xâu trong trie có tiền tố
//                              // là xâu được thể hiện bằng đỉnh hiện tại
//        }
//        nodes[pos].exist++; // Đã tìm được đỉnh tương ứng với xâu s,
//                            // ta tăng biến exist của đỉnh lên 1
//    }
//
//    bool delete_string_recursive(int pos, string& s, int i) { // Trả về liệu đỉnh pos
//                                                              // có bị xóa đi hay không
//        if (i != (int)s.size()) { // Nếu chưa đến đỉnh tương ứng với xâu s
//                                  // thì tiếp tục đệ quy xuống dưới
//            int c = s[i] - 'a';
//            bool isChildDeleted = delete_string_recursive(nodes[pos].child[c], s, i + 1);
//            if (isChildDeleted) nodes[pos].child[c] = -1; // Nếu đỉnh con tương ứng bị xóa thì
//                                                          // ta gán lại đỉnh tương ứng bằng -1
//        }
//        else nodes[pos].exist--; // Nếu đã đến đỉnh tương ứng với xâu s
//                                 // thì ta giảm biến exist của đỉnh đi 1
//
//        if (pos != 0) { // Nếu đỉnh đang xét không phải gốc thì ta giảm biến cnt của đỉnh đi 1
//                        // và kiểm tra đỉnh có bị xóa đi hay không
//                        // Đỉnh bị xóa nếu không còn xâu nào đi qua nó, nói cách khác là
//                        // không còn xâu nào có tiền tố là xâu được thể hiện bởi đỉnh pos
//            nodes[pos].cnt--;
//            if (nodes[pos].cnt == 0) return true;
//        }
//        return false;
//    }
//
//    void delete_string(string s) {
//        if (find_string(s) == false) return; // Kiểm tra xâu s có trong
//                                             // trie hay không
//        delete_string_recursive(0, s, 0); // Gọi hàm đệ quy xóa xâu s khỏi trie
//    }
//
//    bool find_string(string s) {
//        int pos = 0;
//        for (auto f : s) {
//            int c = f - 'a';
//            if (nodes[pos].child[c] == -1) return false;
//            pos = nodes[pos].child[c];
//        }
//        return (nodes[pos].exist != 0); // Kiểm tra có xâu nào
//                                        // kết thúc tại đỉnh này hay không
//    }
//};

#include <bits/stdc++.h>
using namespace std;

const int N = 100003;
int n, x, y, i;
int m[N][3], a, b;
long long ans;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for(i=1; i<=(n<<1); ++i){
		cin >> x >> y;
		if(x < 1) ans += 1 - x, x = 1;
		else if(x > n) ans += x - n, x = n;
		if(y < 1) ans += 1 - y, y = 1;
		else if(y > 2) ans += y - 2, y = 2;
		++m[x][y];
	}
	for(i=1; i<=n; ++i){
		a += m[i][1] - 1, b +=  m[i][2] - 1;
		while(a > 0 and b < 0) --a, ++b, ++ans;
		while(a < 0 and b > 0) ++a, --b, ++ans;
		ans += abs(a) + abs(b);
	}
	cout << ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63