QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405011#3005. MonotonyLspeedAC ✓3090ms199872kbC++143.7kb2024-05-05 06:29:422024-05-05 06:29:42

Judging History

你现在查看的是最新测评结果

  • [2024-05-05 06:29:42]
  • 评测
  • 测评结果：AC
  • 用时：3090ms
  • 内存：199872kb
查看
  • [2024-05-05 06:29:42]
  • 提交

answer

#include <iostream>     // Input/output stream objects
#include <fstream>      // File stream objects
#include <sstream>      // String stream objects
#include <iomanip>      // Input/output manipulators
#include <string>       // String class and functions
#include <vector>       // Dynamic array
#include <list>         // Doubly linked list
#include <set>          // Set container
#include <map>          // Map container
#include <queue>        // Queue container
#include <stack>        // Stack container
#include <algorithm>    // Algorithms on sequences (e.g., sort, find)
#include <cmath>        // Mathematical functions
#include <ctime>        // Date and time functions
#include <cstdlib>      // General purpose functions (e.g., memory management)
#include <cstring>      // C-style string functions
#include <cctype>       // Character classification functions
#include <cassert>      // Assert function for debugging
#include <exception>    // Standard exceptions
#include <functional>   // Function objects
#include <iterator>     // Iterator classes
#include <limits>       // Numeric limits
#include <locale>       // Localization and internationalization
#include <numeric>      // Numeric operations (e.g., accumulate)
#include <random>       // Random number generators
#include <stdexcept>    // Standard exception classes
#include <typeinfo>     // Runtime type information
#include <utility>      // Utility components (e.g., std::pair)
#include <bitset>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < (b); i++)
#define FORE(i, a, b) for(int i = a; i <= (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define x first 
#define y second
#define mp make_pair
#define PI 3.141592653
const double eps = 1e-9;

int r, c;
ll ans;
vector<vector<int>> grid(22, vector<int>(22, 0));
vector<vector<ll>> dp(23, vector<ll>((1<<20) + 10, 0LL));

bool check_mono(int col, int rows) {
    vector<int> num;
    FOR (i, 0, r) if ((1 << i) & rows) num.push_back(grid[i][col]);
    if (sz(num) == 1) return true;
    bool inc = (num[0] < num[1]);
    FOR (i, 1, sz(num) - 1) if (inc != (num[i] < num[i+1])) return false;
    return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> r >> c;
    
    FOR (i, 0, r) FOR (j, 0, c) cin >> grid[i][j];
    
    // preprocess
    // parity[i][j] from j to i (1 = increase, 0 = decrease)
    // vector<int> coord;
    vector<vector<int>> parity(22, vector<int>(22, 0));
    FOR (i, 0, c) FOR (j, i+1, c) {
        FOR (k, 0, r) if (grid[k][j] > grid[k][i]) parity[j][i] += (1 << k);
    }

    FOR (rows, 1, 1 << r) {      
        // FOR (i, 0, c) FOR (j, i+1, c) {
        //     FOR (k, 0, r) if ((rows & (1 << k)) != 0 && grid[k][j] > grid[k][i]) parity[j][i] += (1 << k);
        // }

        // FOR (i, 1, c) FORE (j, 0, i-1) coord.push_back(parity[i][j]);
        // sort(all(coord));
        // coord.resize(unique(all(coord)) - coord.begin());
        // auto get_id = [&](int x) { return lower_bound(all(coord), x) - coord.begin(); };
        // FOR (i, 1, c) FORE (j, 0, i-1) parity[i][j] = get_id(parity[i][j]);

        vector<bool> is_mono(c + 5, true);
        FOR (i, 0, c) is_mono[i] = check_mono(i, rows);
        FOR (i, 0, c) {
            if (!is_mono[i]) continue;
            ans += 1;
            for (int j = 0; j <= i-1; j++) if (is_mono[j]) {
                int curpar = (parity[i][j] & rows);
                ans += dp[j][curpar] + 1;
                dp[i][curpar] += dp[j][curpar] + 1;
            }
        }

        FOR (i, 0, c) {
            for (int j = 0; j <= i-1; j++) {
                dp[i][parity[i][j] & rows] = 0;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 52ms
memory: 199656kb

input:

13 17
155 221 29 114 165 175 120 107 27 134 125 116 11 56 100 20 15
88 128 38 111 198 212 173 136 44 164 64 150 83 19 93 197 194
219 25 16 50 2 55 151 34 163 76 217 209 141 174 80 144 159
60 156 54 149 97 28 102 145 26 35 188 160 65 152 135 6 21
8 62 195 70 127 30 171 205 147 177 210 117 10 103 161 ...

output:

40490

result:

ok answer is '40490'

Test #2:

score: 0
Accepted
time: 249ms
memory: 199792kb

input:

17 13
41 205 162 42 35 147 143 185 89 176 4 103 181
85 115 59 2 182 190 20 142 97 172 31 211 101
154 62 119 82 16 117 1 157 72 3 149 216 21
188 49 202 77 161 160 169 46 79 133 50 113 91
30 71 156 193 92 29 54 187 111 199 80 22 17
209 122 138 127 135 81 53 86 158 145 109 56 6
150 40 15 212 10 186 32 ...

output:

35799

result:

ok answer is '35799'

Test #3:

score: 0
Accepted
time: 30ms
memory: 199648kb

input:

1 1
1

output:

1

result:

ok answer is '1'

Test #4:

score: 0
Accepted
time: 24ms
memory: 199752kb

input:

1 2
1 2

output:

3

result:

ok answer is '3'

Test #5:

score: 0
Accepted
time: 27ms
memory: 199792kb

input:

1 2
2 1

output:

3

result:

ok answer is '3'

Test #6:

score: 0
Accepted
time: 36ms
memory: 199792kb

input:

1 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

output:

1048575

result:

ok answer is '1048575'

Test #7:

score: 0
Accepted
time: 31ms
memory: 199708kb

input:

2 1
1
2

output:

3

result:

ok answer is '3'

Test #8:

score: 0
Accepted
time: 11ms
memory: 199808kb

input:

2 1
2
1

output:

3

result:

ok answer is '3'

Test #9:

score: 0
Accepted
time: 20ms
memory: 199644kb

input:

2 2
1 2
3 4

output:

9

result:

ok answer is '9'

Test #10:

score: 0
Accepted
time: 31ms
memory: 199640kb

input:

2 2
1 3
4 2

output:

9

result:

ok answer is '9'

Test #11:

score: 0
Accepted
time: 16ms
memory: 199792kb

input:

2 2
2 1
4 3

output:

9

result:

ok answer is '9'

Test #12:

score: 0
Accepted
time: 19ms
memory: 199652kb

input:

2 2
3 2
4 1

output:

9

result:

ok answer is '9'

Test #13:

score: 0
Accepted
time: 27ms
memory: 199656kb

input:

2 2
4 3
2 1

output:

9

result:

ok answer is '9'

Test #14:

score: 0
Accepted
time: 12ms
memory: 199652kb

input:

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

output:

225

result:

ok answer is '225'

Test #15:

score: 0
Accepted
time: 28ms
memory: 199768kb

input:

4 4
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13

output:

225

result:

ok answer is '225'

Test #16:

score: 0
Accepted
time: 43ms
memory: 199872kb

input:

4 4
4 5 1 3
11 6 13 10
16 2 9 8
14 15 12 7

output:

110

result:

ok answer is '110'

Test #17:

score: 0
Accepted
time: 207ms
memory: 199756kb

input:

20 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

output:

1048575

result:

ok answer is '1048575'

Test #18:

score: 0
Accepted
time: 2316ms
memory: 199644kb

input:

20 19
180 179 178 177 176 175 174 173 172 190 189 188 187 186 185 184 183 182 181
161 160 159 158 157 156 155 154 153 171 170 169 168 167 166 165 164 163 162
142 141 140 139 138 137 136 135 134 152 151 150 149 148 147 146 145 144 143
123 122 121 120 119 118 117 116 115 133 132 131 130 129 128 127 12...

output:

3485104

result:

ok answer is '3485104'

Test #19:

score: 0
Accepted
time: 2843ms
memory: 199640kb

input:

20 19
9 8 7 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 10
28 27 26 25 24 23 22 21 20 38 37 36 35 34 33 32 31 30 29
47 46 45 44 43 42 41 40 39 57 56 55 54 53 52 51 50 49 48
66 65 64 63 62 61 60 59 58 76 75 74 73 72 71 70 69 68 67
85 84 83 82 81 80 79 78 77 95 94 93 92 91 90 89 88 87 86
104 103 102 101 10...

output:

1702885800

result:

ok answer is '1702885800'

Test #20:

score: 0
Accepted
time: 2358ms
memory: 199640kb

input:

20 19
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 13...

output:

1125119902

result:

ok answer is '1125119902'

Test #21:

score: 0
Accepted
time: 3090ms
memory: 199644kb

input:

20 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
10...

output:

1099509530625

result:

ok answer is '1099509530625'

Test #22:

score: 0
Accepted
time: 2811ms
memory: 199620kb

input:

20 20
56 358 43 382 339 146 206 335 390 285 57 35 252 147 378 106 352 395 129 214
308 166 167 359 207 244 77 181 148 158 227 34 200 125 342 93 122 95 377 228
79 26 268 253 192 84 70 301 384 231 171 198 126 137 237 185 310 242 246 153
115 168 203 346 96 399 306 32 215 138 176 360 303 101 275 332 177 ...

output:

153561

result:

ok answer is '153561'
English 繁體中文 简体中文

伺服器時間: 2025-02-01 21:01:59 | 開源專案