글 읽기 - 왜 메모리초과가 뜰까요 ??

upsk1 1년 전 0

전체적인 로직은 각 기울기에 대응하는 set을 만들어 좌표압축 후 주어진 조건대로 입력을 처리한 소스입니다..

혹시 왜 메모리 초과가 떳을까요 ??

#include <bits/stdc++.h>
using namespace std;
multiset<pair<int, int>> Set1[100010], Set2[100010];
string s;
map<int, int> Map1,Map2;
pair<int, int> pos[100001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    cin >> s;
    int tidx1 = 1, tidx2 = 1;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        int num1 = x - y;
        if (Map1[num1] == 0) {
            Map1[num1] = tidx1++;
        }
        num1 = Map1[num1];
        int num2 = x + y;
        if (Map2[num2] == 0) {
            Map2[num2] = tidx2++;
        }
        num2 = Map2[num2];
        Set1[num1].insert({ x,y });
        Set2[num2].insert({ x,y });
        pos[i].first = x; pos[i].second = y;
    }
    int nowx = pos[0].first, nowy = pos[0].second;
    for (int i = 0; i < k; i++) {
        //A : set1 right
        //B : set2 right
        //C : set2 left
        //D : set1 left
        int idx1 = Map1[{nowx - nowy}];
        int idx2 = Map2[{nowx + nowy}];
        int nextx = -1, nexty = -1;
        if (s[i] == 'A') {
            auto it = Set1[idx1].find({ nowx,nowy });
            auto it2 = Set1[idx1].upper_bound({ nowx,nowy });
            if (it2 != Set1[idx1].end()) {
                nextx = (*it2).first; nexty = (*it2).second;
                Set1[idx1].erase(it);
                it = Set2[idx2].find({ nowx,nowy });
                Set2[idx2].erase(it);
            }
        }
        else if (s[i] == 'D') {
            auto it = Set1[idx1].lower_bound({ nowx,nowy });
            auto it2 = prev(it);
            if (it2 != Set1[idx1].end()) {
                nextx = (*it2).first; nexty = (*it2).second;
                Set1[idx1].erase(it);
                it = Set2[idx2].find({ nowx,nowy });
                Set2[idx2].erase(it);
            }
        }
        else if (s[i] == 'B') {
            auto it = Set2[idx2].find({ nowx,nowy });
            auto it2 = Set2[idx2].upper_bound({ nowx,nowy });
            if (it2 != Set2[idx2].end()) {
                nextx = (*it2).first; nexty = (*it2).second;
                Set2[idx2].erase(it);
                it = Set1[idx1].find({ nowx,nowy });
                Set1[idx1].erase(it);
            }
        }
        else {
            auto it = Set2[idx2].lower_bound({ nowx,nowy });
            auto it2 = prev(it);
            if (it2 != Set2[idx2].end()) {
                nextx = (*it2).first; nexty = (*it2).second;
                Set2[idx2].erase(it);
                it = Set1[idx1].find({ nowx,nowy });
                Set1[idx1].erase(it);
            }
        }
        if (nextx != -1) {
            nowx = nextx;
            nowy = nexty;
        }
        //cout << s[i] << ' ' << nowx << ' ' << nowy << '\n';
        //cout << "Set1 \n";
        //for (auto itt = Set1[idx1].begin(); itt != Set1[idx1].end(); itt++) {
        //    cout << (*itt).first << ' ' << (*itt).second << '\n';
        //}
        //cout << "Set2 \n";
        //for (auto itt = Set2[idx2].begin(); itt != Set2[idx2].end(); itt++) {
        //    cout << (*itt).first << ' ' << (*itt).second << '\n';
        //}
        //cout << '\n';
    }
    cout << nowx << ' ' << nowy << '\n';

}

upsk1 1년 전 0

djm03178 님이 알려주신건데 begin일때 prev 함수를 쓰면 안됩니다. 다시 한번 더 감사드립니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 메모리초과가 뜰까요 ??

upsk1 1년 전 0

upsk1 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말