समस्या
एक बहुत बड़े स्टेडियम का बैठने का चार्ट ज़्यादातर खाली है, इसलिए हर cell को store करना memory की बर्बादी है। SparseGrid सिर्फ़ उन cells को store करता है जिनमें non-zero मान है; बाकी हर cell 0 है। Grid की शुरुआत rows पंक्तियों, cols कॉलमों और बिना किसी store किए cell के होती है। इन operations को क्रम से process कीजिए:
set r c v: cell (r, c) का मानvहो जाता है। 0 set करने पर cell storage से हट जाता है।get r c: cell (r, c) का मान आउटपुट कीजिए।count: कितने cells non-zero हैं, यह आउटपुट कीजिए।row_sum r: पंक्तिrके मानों का योग आउटपुट कीजिए।width: कॉलमों की मौजूदा संख्या आउटपुट कीजिए।remove_col c: कॉलमcहटा दीजिए। उसके cells गायब हो जाते हैं, उसके दाईं ओर का हर cell एक कॉलम बाईं ओर खिसक जाता है, और grid में एक कॉलम कम हो जाता है।
पंक्तियाँ और कॉलम 0 से गिने जाते हैं, और operation के समय हर index grid के अंदर होता है।
sparse_grid(rows, cols, operations) लिखिए।
इनपुट
rows: पंक्तियों की संख्या।
cols: कॉलमों की शुरुआती संख्या।
operations: operations, जिन्हें क्रम से process करना है।
आउटपुट
get, count, row_sum और width के आउटपुट उसी क्रम में लौटाइए जिसमें वे होते हैं।
सीमाएँ
1 ≤ rows ≤ 1,000,000
1 ≤ cols ≤ 1,000,000
0 ≤ operations की संख्या ≤ 1,000
−1,000,000 ≤ v ≤ 1,000,000
उदाहरण
इनपुट:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
अपेक्षित आउटपुट:
expected = [7, 3, 0]
इनपुट:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {7, 3, 0};
इनपुट:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};
अपेक्षित आउटपुट:
long[] expected = new long[] {7, 3, 0};
व्याख्या
पंक्ति 0 में 5 और 2 हैं, इसलिए उसका योग 7 है; तीन cells store हैं; (1, 1) कभी set नहीं हुआ, इसलिए वह 0 है।
इनपुट:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
अपेक्षित आउटपुट:
expected = [9, 2, 1]
इनपुट:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {9, 2, 1};
इनपुट:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};
अपेक्षित आउटपुट:
long[] expected = new long[] {9, 2, 1};
व्याख्या
कॉलम 0 हटाने से 4 मिट जाता है और 9 कॉलम 2 से कॉलम 1 पर खिसक जाता है, इसलिए get 1 1 का जवाब 9 है, width 2 है और एक cell बचता है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
(पंक्ति, कॉलम) से मान वाला map अच्छा काम करता है; key न होने का मतलब 0 है।
संकेत 2
किसी cell को 0 set करने पर उसे हटा दीजिए ताकि `count` सही रहे।
संकेत 3
कॉलम हटाने पर map दोबारा बनाइए: उस कॉलम को हटाइए और उससे बड़े कॉलम नंबरों को एक कम कर दीजिए।
अपेक्षित जटिलता
समय O(q × s), अतिरिक्त स्थान O(s), s = store किए गए cells
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।