O(mn²)竟然过了。。。

2huk @ 2023-01-28 11:14:56

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

#define int long long
#define TRACE 1
#define tcout TRACE && cout
#define el printf("\n")
#define inf 0x7fffffff

int n, m;
int a[1010][1010];
int x1, x2, y1, y2; 

signed main()
{
    cin >> n >> m;
    while(m--){
        cin >> x1 >> y1 >> x2 >> y2;
        for(int i=x1; i<=x2; i++){
            for(int j=y1; j<=y2; j++){
                a[i][j]++;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout << a[i][j] << ' ';
        }
        el;
    }
    return 0;
}

by Limitless_lmw @ 2023-01-28 11:40:14

楼你【】下

by LCATreap @ 2023-01-28 11:44:28

这个本来就跑不满吧（

内存访问连续，而且 x1,x2,y1,y2 这些本来就不满。

但是最大点就 200 多 ms 确实这数据弱得有点匪夷所思了，大概这道题本来就是放暴力过的？

by chen_zhe @ 2023-01-28 11:46:36

@wqlGZZC 我的理解是数据比较随机，这样每次平均是跑 n^2/4 的量，但是其实把这 4 倍乘回去照样也能在 1s 内跑过。。

现在的问题是内存访问连续而且操作不多的题目，n=1000 已经挡不住暴力了。可能以后要开到 n=2000 卡小常数 O(n^3)。

by myee @ 2023-01-28 11:50:35

把 m 开到 10^6 啥事没有。

by Albert_Wei @ 2023-01-28 11:51:18

@chen_zhe 卡掉吧，缩小时限，因为这本来就不是正解。

by myee @ 2023-01-28 11:53:06

以及题目背景可以改改了，感觉是普及组难度。

by cff_0102 @ 2023-01-28 11:54:45

对诶，这个就是正常的噗叽难度

by yinhee @ 2023-01-28 12:15:40

@chen_zhe 指一般常数中等情况跑不过去

我说明了这题常数实在小，是特例

顺便说一下，提高组D2T1是不是该改改

by yinhee @ 2023-01-28 12:22:50

@chen_zhe lg评测姬不是1s跑1.2e9次+么，这也不一定卡不掉罢

不如加一组试试

by Latsukisan @ 2023-04-17 20:26:11

@chen_zhe m取1000的最糟糕情况下不是跑不过吗?